January 2014 - mathfun@mailman.xmission.com

[math-fun] HAKMEM's missing entry for "ROP"
by Henry Baker 27 Jan '14

27 Jan '14

"Tails You Lose" What I'm going to describe is about 10 years old, but may be considerably older (please let me know!). Consider the plight of a virus in a biological system. The virus has to make copies of itself, but it can't afford to carry around the complete set of instruction bits necessary to describe to the host organism how to do this. In particular, the virus has to tell the host organism how to make various proteins in various sequences to force the host to build copies of the virus, and the virus doesn't want to have to describe every single needed protein within the virus's own DNA/RNA. To reduce the number of bits that the virus has to carry, the virus relies on intimate knowledge of the existing host's own DNA & RNA, so that it can "repurpose" various DNA & RNA subsequences for its own uses. In many cases, it won't even matter whether the subsequences within the host's DNA & RNA are "aligned" properly or not; the virus will only care that the subsequences it needs already exist within the host's DNA & RNA. The virus is thus performing a kind of "rsync" algorithm, which was originally developed to save bandwidth during the transmission of information from one computer to another by taking advantage of subsequences of bits that already existed within the receiving computer. Rsynch only transmits the "instructions" for constructing the intended sequence from bits and subsequence pieces already present on the receiving computer. http://en.wikipedia.org/wiki/Rsync Thus, if most of the bits the virus already requires are already present (perhaps in pieces) as subsequences of the host's DNA & RNA, the virus only has to contain the missing bits, together with enough information to assemble the complete sequences from these subsequence bits and pieces. It should be clear that the virus has traded off ease of transmission for specificity of hosts, since only those hosts that have its "missing" bits will be capable of reproducing the virus. A similar situation exists for computer viruses today. While memory capacity and transmission bandwidth of today's computers are very generous, there are severe limitations on the types of sequences that are allowed to execute. In particular, modern (and not-so-modern!) computers typically have read/write/execute permissions on pages in memory. If a page is designated "rx" (read/execute), it can be executed, while if a page is designated as "rw", it can be read and written but not executed. Modern computers (for a huge number of reasons), do not allow write access to executable pages, and it is quite difficult to change the permission status of a page from writable to executable. Similarly, (and for many of the same reasons) these computers do not allow "instructions" on writable pages to be executed. This page permission structure would seem to eliminate the possibility of executing arbitrary tasks not already present in the non-writable executable pages, but this is incorrect! Modern computer viruses can do the same thing that biological viruses can do: find _existing_ bit sequences & repurpose them for the virus's own computation. While these existing bit sequences may not be the most efficient or elegant means to achieve the virus's ends, it doesn't matter, because the virus's life & progeny depend upon these possibly-clumsy mechanisms. Step 1. Find useful subsequences already extant on the host. These subsequences will be called "widgets". In the case of computer programs, we need to find usable sequences of bits already extant _within executable pages_ that can be used to construct Turing-complete computation. This is due to the limitation that only instruction sequences on executable pages are allowed to be executed. Given the multi-gigabyte size and complexity of modern operating systems, this is actually a quite easy task, because we're approximating the "infinite monkey theorem", wherein enough (Seattle-based) monkeys with computer consoles can construct every sequence of instructions. http://en.wikipedia.org/wiki/Infinite_monkey_theorem For our usable widgets, we're going to be looking for sequences of instructions that end in a "return" instruction, because we will need this "return" instruction to link these subsequence widgets together in the fashion of "threaded code interpreters". http://en.wikipedia.org/wiki/Threaded_code Some of the best sources of "return-rich" code sequences exist in "shared libraries". Because these are libraries, they tend to be collections of subroutines, each of which terminates in a "return" instruction, and since these are _shared_ they reside on read-only, _executable_ memory pages. Furthermore, since these are libraries, they tend to be quite constant for many, many years, and hence can be relied upon to contain constant sequences. Note that _complete_ library subroutines are less interesting for the virus's purposes, than are _tails_ of library subroutines. The main entry point of a subroutine expects arguments in standard locations, but by entering this instruction sequence further down near the end, the subroutine is more likely to be utilizing values in non-standard locations (including memory locations). Step 2. Use a Turing-complete set of widgets as a new "instruction set" for a "threaded code interpreter". The typical widget consists of a number of instructions which manipulate memory and/or registers, followed by a return instruction which pops an address from the stack and jumps to this address to resume execution. A return instruction that returns to an address stored in a register is just as useful. Due to the restriction that execution is only possible when instructions are fetched from "executable" memory pages, our virus must guarantee that all such "return" addresses fall within these executable memory pages. There are several ways to implement if-then-else with these widgets. One can adjust the stack pointer by a variable amount to achieve the effect of a "skip" instruction. One can also execute both arms of a conditional and arrange to use only the result of the correct branch. Thus, our virus fashions a Forth/Postscript-like stack machine out of these widgets which loads arguments into registers or onto the stack, loads the address of the next widget onto the stack, loads the address of the current widget onto the stack, and then "returns" to this address just pushed onto the stack. http://en.wikipedia.org/wiki/Forth_(programming_language) http://en.wikipedia.org/wiki/PostScript (Forth-type stack languages themselves are considerably older than computers; they are a form of "combinators". http://en.wikipedia.org/wiki/Combinatory_logic ) In essence, this "return-oriented programming" (ROP) dispenses with the existing "call" instruction, and relies exclusively on the "return" instruction for all calls, returns and jumps. Unfortunately, return-oriented programming is not just a theoretical construct, but a very real mechanism by which modern computer viruses and worms can take over a machine. If there is even _one_ "buffer overflow" programming error in the code, a malicious programmer can construct a long string of bytes which encodes his/her malicious program in this "widget" stack machine, and causes it to start running when the subroutine receiving this long string attempts to return. At that point, this widget stack machine program starts executing, and performs enough computation to eventually constructs a system call which changes a page from writable to executable, and the machine is now completely compromised. Note that return-oriented programming might be stopped by making serious use of a "COMEFROM" (instead of GOTO) instruction. http://en.wikipedia.org/wiki/COMEFROM Alternately, it might be possible to use an analogy of the "XOR linked list" hack, only using instruction lists as linked lists, in order to defeat enetering code at the wrong places and/or from the wrong places. (Wasn't the list XOR hack part of original HAKMEM, or perhaps in KnuthV1 ?) http://en.wikipedia.org/wiki/XOR_linked_list http://en.wikipedia.org/wiki/Return-oriented_programming http://cseweb.ucsd.edu/~hovav/dist/sparc.pdf

3 3

[math-fun] The Combinatorial Statistic Finder
by Victor Miller 25 Jan '14

25 Jan '14

I just came across this website: http://www.findstat.org/ . It looks rather interesting, especially to funsters. Victor

4 5

Re: [math-fun] pant versus pants
by Adam P. Goucher 25 Jan '14

25 Jan '14

> Joerg wrote: > P.S.: does anyone know anybody who recollects asking for their own name? Haha, I have an amusing story pertaining to this. Before I was aware of my own name, or even of the concept of having a name, I had the misconception that `Adam!' meant `behave yourself!'; this was a rather logical conclusion given the fact that it was often shouted by my parents whenever I performed an indiscretion. Sincerely, Adam P. Goucher

4 3

[math-fun] What is Joerg Arndt's name?
by Warren D Smith 25 Jan '14

25 Jan '14

> P.S.: does anyone know anybody who recollects asking for their own name? > Here is my story: > Got aware that I got a name. > Asked my mother what it was, but immediately forgot. > Asked again, wishing to be able to recall it, but > still forgot after a few minutes. > Getting annoyed with myself for having forgotten. > Asked again, then repeated it over and over to myself. > Remembered it from there, success! --this is quite impressive memory. "Infantile amnesia" afflicts most (all?) people preventing any event-memory before age of about 3. http://en.wikipedia.org/wiki/Childhood_amnesia There are occasionally those whose claim to remember back much further, but it is tough for them to prove it if so...

4 3

Re: [math-fun] pant versus pants
by Bill Gosper 25 Jan '14

25 Jan '14

On 2014-01-24 18:48, Huddleston, Scott wrote: > Thanks to Allan Sherman's comedy lyrics, I grew up thinking "half a > pairs of scissors is a single sciss" :-) > It's actually the rarely used "scissor". > > -----Original Message----- > From: math-fun-bounces(a)mailman.xmission.com > [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of meekerdb > Sent: Friday, January 24, 2014 5:59 PM > To: math-fun > > They say "pants" because they have two legs, the same way they say > "pliers" and "scissors". > > Brent Meeker > > On 1/24/2014 6:38 AM, Adam P. Goucher wrote: >> Quite a lot of Anglo-American confusion arises from the fact that >> American `pants' are trousers, whereas British `pants' are underwear. >> >> Of course, I'm surprised that Americans don't say `pant' instead. (!) >> >> >> Sincerely, >> >> >> Adam P. Goucher >> >> http://cp4space.wordpress.com >> >>> ----- Original Message ----- >>> From: W. Edwin Clark >>> Sent: 01/24/14 06:12 AM >>> To: math-fun >>> Subject: [math-fun] math versus maths >>> >>> This video defends the American way. >>> <https://www.youtube.com/watch?v=SbZCECvoaTA> Perhaps stolen years earlier from Roger Price: http://capj.livejournal.com/11301.html --rwg While "aluminum" may have been a mistake, we don't say plumbium, stannium, aurium, or argentium. I grew up thinking Saksfifth was an avenue.

7 6

Re: [math-fun] pant versus pants
by Adam P. Goucher 25 Jan '14

25 Jan '14

Quite a lot of Anglo-American confusion arises from the fact that American `pants' are trousers, whereas British `pants' are underwear. Of course, I'm surprised that Americans don't say `pant' instead. (!) Sincerely, Adam P. Goucher http://cp4space.wordpress.com > ----- Original Message ----- > From: W. Edwin Clark > Sent: 01/24/14 06:12 AM > To: math-fun > Subject: [math-fun] math versus maths > > This video defends the American way. > <https://www.youtube.com/watch?v=SbZCECvoaTA> > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 2

[math-fun] maths-fun? math-funs?
by Warren D Smith 24 Jan '14

24 Jan '14

Actually, I settled on a hybrid US-UK method myself. I say "Let's do some math" and "math is fun" and "the math concludes that..." But I also say "Amer. J. Maths." I feel the latter is superior for aiding the reader to reconstruct the full journal name. Journal abbreviations should not be used unless provide clear unique reconstructibility. -- Warren D. Smith

4 3

[math-fun] math versus maths
by W. Edwin Clark 24 Jan '14

24 Jan '14

This video defends the American way. <https://www.youtube.com/watch?v=SbZCECvoaTA>

2 1

[math-fun] 440 steps
by Hans Havermann 22 Jan '14

22 Jan '14

Ray Chandler and I recently enumerated all 15095 terms of A114440. [Consider a number divided by the sum of its (base ten) digits. If it goes evenly, repeat the procedure with the quotient. Continue thus until either the quotient arrived at is not evenly divisible by the sum of its digits, or the number 1 is reached. A114440 lists numbers that reach 1.] There are no numbers that require more than 440 steps to reach 1. There are four that take exactly 440 steps, the largest being 108446423039535872993215143801708248788897518439196551865815224471960229150134987551824227831682497439642537447219998905173574636075570938726770415637566547495970738297545359694233469258248066044412311789418336202690430748419494353337428921317543676766009509734177677473770421445221936204214282140014849868367338680549949846121648321743392211378370176998833209921206655217464739831625543921041252648766408996885700710913879052486492812317563281491911243925427378877369142768640406323066824797472131147967140977568412789256710759050409656222035706522393291677890231411695839455220245836396027648440861440543344125146667943578032458072195974008992176685068654594958348314899096787905903269227303672466102253350452074656943436672832591933669507219965857301188944026241623994044261445035477186928141071384209363011062866156003328225359218417581786664993612723261535530033504534359456197194706824538502279255382972206034525278814354951808365156295137852239659582806470869382588169461649156300693104208166972689007486529034860083473459976647843779025561266682409926743436435548435186073490637074087381530918243621501901195914047236424084375593247227970958601139272341797395550196589930052572977357562548306987001964447384676858917584692194740403103300719776568071910636020311087045555588606644758684325277244510326965842198914723217408000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.

1 0

[math-fun] Three-dimensional Topological Dirac Semimetal Na3Bi
by Warren D Smith 22 Jan '14

22 Jan '14

http://arxiv.org/abs/1310.0391 --what good is this stuff? Can anybody explain?

2 1