Trying to Meltdown in Java -failing. Probably

Meltdown has made for an "interesting" week in computing, as everyone is learning about/revising their knowledge of Speculative Execution. FWIW, I'd recommend the latest version of Patterson and Hennessey, Computer Architecture A Quantitative Approach. Not just for its details on speculative execution, but because it is the best book on microprocessor architecture and design that anyone has ever written, and lovely to read. I could read it repeatedly and not get bored.(And I see I need to get the 6th edition!)



This weekend, rather than read Patterson and Hennessey(*) I had a go to see if you could implement the meltdown attack in Java, hence in mapreduce, spark, or other non-native JAR

My initial attempt failed provided the part only speculates one branch in.

More specifically "the range checking Java does on all array accesses blocks the standard exploit given steve's assumptions". You can speculatively execute the out of bounds query, but you can't read the second array at an offset which will trigger $L1 cache loading.

If there's a way to do a reference to two separate memory locations which doesn't trigger branching range checks, then you stand a chance of pulling it off. I tried that using the ? : operator pair, something like

String ref = data ? refA : ref B;

which I hoped might compile down to something like


mov ref, refB
cmp data, 0
cmovnz ref, refB

This would do the move of the reference in the ongoing speculative branch, so, if "ref" was referenced in any way, trigger the resolution

In my experiment (2009 macbook pro with OSX Yosemite + latest java 8 early access release), a branch was generated ... but there are some refs in the open JDK JIRA to using CMOV, including the fact that hotspot compiler may be generating it if it things the probability of the move taking place is high enough.

Accordingly, I can't say "the hotspot compiler doesn't generate exploitable codepaths", only "in this experiment, the hotspot compiler didn't appear to generate an exploitable codepath".

Now the code is done, I might try on a Linux VM with Java 9 to see what is emitted

1. If you can get the exploit in, then you'd have access to other bits of the memory space of the same JVM, irrespective of what the OS does. That means one thread with a set of Kerberos tickets could perhaps grab the secrets of another. IT'd be pretty hard, given the way the JVM manages objects on the heap: I wouldn't know where to begin, but it would become hypothetically possible.
2. If you can get native code which you don't trust loaded into the JVM, then it can do whatever it wants. The original meltdown exploit is there. But native code running in JVM is going to have unrestricted access to the entire address space of the JVM -you don't need to use meltdown to grab secrets from the heap. All meltdown would do here is offer the possibility of grabbing kernel space data —which is what the OS patch does.

Anyway, I believe my first attempts failed within the context of this experiment.

Code-wise, this kept me busy on Sunday afternoon. I managed to twist my ankle quite badly on a broken paving stone on the way to patisserie on Saturday, so sat around for an hour drinking coffee in Stokes Croft, then limped home, with all forms of exercise crossed off the TODO list for the w/e. Time for a bit of Java coding instead, as a break for what I'd been doing over the holiday (C coding a version of Ping which outputs CSV data and a LaTeX paper on the S3A committers)

It took as much time trying get hold of the OS/X disassembler for generated code as it did coding the exploit. Why so? Oracle have replaced all links in Java.sun.net which would point to the reference dynamic library with a 302 to the base Java page telling you how lucky you are that Java is embedded in cars. Or you see a ref to on-stack-replacement on a page in Project Kenai, under a URL which starts with https://kenai.com/, point your browser there and end up on http://www.oracle.com/splash/kenai.com/decommissioning/index.html and the message "We're sorry the kenai.com site has closed."

All the history and knowledge on JVM internals and how to work there is gone. You can find the blog posts from four years ago on the topic, but the links to the tools are dead.

This is truly awful. It's the best argument I've seen for publishing this info as PDF files with DOI references, where you can move the artifact around, but citeseer will always find it. If the information doesn't last five years, then

The irony is, it means that because Oracle have killed all those inbound links to Java tools, they're telling the kind of developer who wants to know these things to go away. That's strategically short-sighted. I can understand why you'd want to keep the cost of site maintenance down, but really, breaking every single link? It's a major loss to the Java platform —especially as I couldn't even find a replacement.

I did manage to find a copy of the openjdk tarball people send you could D/L and run make on, but it was on a freebsd site, and even after a ./Configure && make, it broke trying to create a bsd dynlib. Then I checked out the full openjdk source tree, branch -8, installed the various tools and tried to build there. Again, some error. I ended up finding a copy of the needed hsdis-amd64.dylib library on Github, but I had to then spend some time looking at evolvedmicrobe's work &c to see if I could trust this to "probably" not be malware itself. I've replicated the JAR in the speculate module, BTW.

Anyway, once the disassembler was done and the other aspects of hotspot JIT compilation clear (if you can't see the method you wrote, run the loop a few thousand more times), I got to see some well annotated x86-64 assembler. Leaving me with a new problem: x86-64 assembler. It's a lot cleaner than classic 32 bit x86: having more registers does that, especially as it gives lots of scope for improving how function parameters and return values are managed.

What next? This is only a spare time bit of work, and now I'm back from my EU-length xmas break, I'm doing other things. Maybe next weekend I'll do some more. At least now I know that exploiting meltdown from the JVM is not going be straightforward.

Also I found it quite interesting playing with this, to see when the JVM kicks out native code, what it looks like. We code so far from the native hardware these days, its too "low level". But the new speculation-side-channel attacks have shown that you'd better understand modern CPU architectures, including how your high-level code gets compiled down.

I think I should submit a berlin buzzwords talk on this topic.

(*) It is traditional to swap the names of the author on every use. If you are a purist you have to remember the last order you used.

Speculation

Speculative execution has been intel's strategy for keeping the x86 architecture alive since the P6/Pentium Pro part shipped in '95.

I remember coding explicitly for the P6 in a project in 1997; HPLabs was working with HP's IC Division to build their first CMOS-camera IC, which was an interesting problem. Suddenly your IC design needs to worry about light, aligning the optical colour filter with the sensors, making sure it all worked.



I ended up writing the code to capture the raw data at full frame rate, streaming to HDD, with an option to alternatively render it with/without the colour filtering (algorithms from another bit HPL team). Which means I get to nod knowingly when people complain about "raw" data. Yes, it's different for every device precisely because its raw.

The data rates of the VGA-resolution sensor via the PCI boards used to pull this off meant that a both cores of a multiprocessor P6 box were needed. It was the first time I'd ever had a dual socket system, but both sockets were full with the 150MHz parts and with careful work we could get away with the "full link rate" data capture which was a core part of the qualification process. It's not enough to self test the chips any more see, you need to look at the pictures.

Without too many crises, everything came together, which is why I have a framed but slightly skewed IC part to hand. And it's why I have memories of writing multithreaded windows C++ code with some of the core logic in x86 assembler. I also have memories of ripping out that ASM code as it turned out that it was broken, doing it as C pointer code and having it be just as fast. That's because: C code compiled to x86 by a good compiler, executed on a great CPU, is at least performant as hand-written x86 code by someone who isn't any good at assembler, and can be made to be correct more easily by the selfsame developer.

150 MHz may be a number people laugh at today, but the CPU:RAM clock ratios weren't as bad as they are today: cache misses are less expensive in terms of pipeline stalls, and those parts were fast. Why? Speculative and out of order execution, amongst other things

1. The P6 could provisionally guess which way a branch was going to go, speculatively executing that path until it became clear whether or not the guess was correct -and then commit/abort that speculative code path.
2. It uses a branch predictor to make that guess on the direction a branch was taken, based on the history of previous attempts, and a default option (FWIW, this is why I tend to place the most likely outcome first in my if() statements; tradition and superstition).
3. It could execute operations out of order. That is, it's predecessor, the P5, was the last time mainstream intel desktop/server parts executed x86 code in the order the compiler generated them, or the human wrote them.
4. register renaming meant that even though the parts had a limited set of registers, those OOO operations could reuse the same EAX, EBX, ECX registers without problems.
5. It had caching to deal with the speed mismatch between that 150 MHz CPU & RAM.
6. It supported dual CPU desktops, and I believe quad-CPU servers too. They'd be called "dual core" and "quad core" these days and looked down at.

Being the first multicore system I'd ever used, it was a learning experience. First was learning how too much windows NT4 code was still not stable in such a world. NTFS crashes with all all volumes corrupted? check. GDI rendering triggering kernel crash? check. And on a 4-core system I got hold of, everything crashed more often. Lesson: if you want a thread safe OS, give your kernel developers as many cores as you can.

OOO forced me to learn about the x86 memory model itself: barrier opcodes, when things could get reordered and when they wouldn't. Summary: don't try and be clever about synchronization, as your assumptions are invalid.

Speculation is always an unsatisfactory solution though. Every mis-speculation is lost cycles. And on a phone or laptop, that's wasted energy as much as time. And failed reads could fill up the cache with things you didn't want. I've tried to remember if I ever tried to use speculation to preload stuff if present, but doubt it. The CMOV command was a non-branching conditional assignment which was better, even if you had to hand code it.  The PIII/SSE added the PREFETCH opcode so you could a non-faulting hinted prefetch which you could stick into your non-branching code, but that was a niche opcode for people writing games/media codecs &c. And as Linus points out, what was clever for one CPU model turns out to be a stupid idea a generation later. (arguably, that applies to Itanium/IA-64, though as it didn't speculate, it doesn't suffer from the Spectre & Meltdown attacks).

Speculation, then: a wonderful use of transistors to compensate for how we developers write so many if() statements in our code. Wonderful, it kept the x86 line alive and so helped Intel deliver shareholder value and keep the RISC CPU out of the desktop, workstation and server businesses. Terrible because :"transistors" is another word for "CPU die area" with its yield equations and opportunity cost, and also for "wasted energy on failed speculations". If we wrote code which had fewer branches in it, and that got compiled down to CMOV opcodes, life would be better. But we have so many layers of indirection these days; so many indirect references to resolve before those memory accesses. Things are probably getting worse now, not better.

This week's speculation-side-channel attacks are fascinating then. These are very much architectural issues about speculation and branch prediction in general, rather than implementation details. Any CPU manufacturer whose parts do speculative execution has to be worried here, even if there's no evidence that your shipping parts aren't vulnerable to the current set of attacks. The whole point about speculation is to speed up operation based on the state of data held in registers or memory, so the time-to-execute is always going to be a side-channel providing information about the data used to make a branch.


The fact that you can get at kernel memory, even from code running under a hypervisor, means, well, a lot. It means that VMs running in cloud infrastructure could get at the data of the host OS and/or those of other VMs running on the same host (those S3 SSE-C keys you passed up to your VM? 0wned, along with your current set of IAM role credentials). It potentially means that someone else's code could be playing games with branch prediction to determine what codepaths your code is taking. Which, in public cloud infrastructure is pretty serious, as the only way to stop people running their code alongside yours is currently to pay for the top of the line VMs and hope they get a dedicated part. I'm not even sure that dedicated cores in a multicore CPU are sufficient isolation, not for anything related to cache-side-channel attacks (they should be good for branch prediction, I think, if the attacker can't manipulate the branch predictor of the other cores).

I can imagine the emails between cloud providers and CPU vendors being fairly strained, with the OEM/ODM teams on the CC: list. Even if the patches being rolled out mitigate things, if the slowdown on switching to kernelspace is as expensive as hinted, then that slows down applications, which means that the cost of running the same job in-cloud just got more expensive. Big cloud customers will be talking to their infrastructure suppliers on this, and then negotiating discounts for the extra CPU hours, which is a discount the cloud providers will expected to recover when they next buy servers. I feel as sorry for the cloud CPU account teams as I do for the x86 architecture group.

Meanwhile, there's an interesting set of interview questions you could ask developers on this topic.

1. What does the generated java assembly for the Ival++ on a java long look like?
2. What if the long is marked as volatile?
3. What does the generated x86 assembler for a Java Optional<AtomicLong> opt.map(AtomicLong::addAndGet(1)) look like?
4. What guarantees do you get about reordering?
5. How would you write code which attempted to defend against speculation timing attacks?
   

I don't have the confidence to answer 1-4 myself, but I could at least go into detail about what I believed to be the case for 1-3; for #4 I should do some revision.

As for #5, defending. I would love to see what others suggest. Conditional CMOV ops could help against branch-prediction attacks, by eliminating the branches. However, searching for references to CMOV and the JDK turns up some issues which imply that branch prediction can sometimes be faster...", including "JDK-8039104. Don't use Math.min/max intrinsic on x86" it may be that even CMOV gets speculated on; with the CPU prefetching what is moved and keeping the write uncommitted until the state of the condition is known.

I suspect that the next edition of Hennessy and Patterson, "Computer Architecture, a Quantitative Approach" will be covering this topic.I shall look forward to with even greater anticipation than I have had for all the previous, beloved, versions.

As for all those people out there panicking about this, worrying if their nearly-new laptop is utterly exposed? You are running with Flash enabled on a laptop you use in cafe wifis without a VPN and with the same password, "k1tten",  you use for gmail and paypal. You have other issues.

Enterprise Hadoop: yes, but how are you going to fix it?

EMC's Pivotal HD has started a lot of debate as to whether building on top of Hadoop can be considered being part of a Hadoop ecosystem or whether it's an attempt to co-opt it: to do something and claim that it is part of a bigger system.

Can you say you are "part of the Hadoop stack" when all you are doing a closed source layer on top? I think that's quite nuanced, and depends on what you do -and how it's interpreted.

1. The Apache License grants everyone the freedom to take the source away and do anything they want with it
2. There is no requirement for you to contribute a single line of code back; a single bug report. 

This is a difference between the ASF license and GPL-licensed software which you redistribute: with GPL code the changes must (somehow) be published. 

Other aspects of the ASF license:

1. You can't abuse ASF brand names, which in the Apache Hadoop world means you can't use Apache Hadoop, Apache HBase, Apache Mahout, Giraph, Apache Pig, Apache Hive, etc in your product names. There are some excellent guidelines on this in the wiki page Defining Hadoop -and if you want actual feedback, email the trademarks@ list. It may seem that doing so removes the secrecy/surprise factor of your product announcement, but it's better that than a hurried renaming of all your product and documentation.
2. If you sue other users of the product over patents of yours that you believe apply to the technology -you revoke your own right to the software. I haven't known that to happen with Apache products -though the Oracle/Google lawsuit did cover copyright of APIs and reimplementations thereof. If APIs ever became copyrightable, then decades of progress in the computing industry will grind to halt.

People are also free to look at Apache APIs and clean-room re-implement them; you just can't use the Apache product names at that point. Asserting compatibility becomes indefensible: if you look at the ASF JIRAs, even 100% compatibility across versions is hard to achieve -that's with the same source tree. It's not the binary signature that is (usually) the problem, its what happens afterwards that's trouble. Little things like whether renaming a file is atomic, or what happens when you ask for the block locations of a directory.

Now, what about introducing a closed source product on top of Hadoop and saying you are part of the hadoop ecosystem, that you have x-hundred people working on Hadoop?

This is where it gets tricky.

Some people say "it's like building on Linux" -and there are some very big closed applications that run on Linux. A big one that springs to mind is Oracle RDBMs.

Are the thousands of people who work on Oracle-on-Linux "working on Linux"? Are they working on "Oracle on Linux", or are they working "on Oracle", on Linux?

Whatever way you look at it, those people aren't working in the Linux OS, just on something that runs on top of it . Would you call it part of the Linux "stack", the way MySQL and Apache HTTPD are?

Personally: I have no idea.




What probably doesn't happen from Oracle's work is any direct feedback from their application into the OS. [Correction: it does, thx @tlipcon]. I also doubt that RedHat, Novell and others regression test Oracle RDBMS on their latest builds of Linux. By their very nature, closed-source applications fall out of the normal OSS regression and release test processes, that rely not only on the open source trees, but the open test suites. This is also why Oracle's actions in not releasing all tests for MySQL seems so short sighted: it may hurt MariaDB, but it also hinders Linux regression testing.


Breaking that link between the OS and the application means that Oracle have not been in the position to rapidly adapt to problems in the OS and filesystem, because there's no way to push their issues back upstream, to get changes in, to get new releases out in a hurry to fix a problem with their application or hardware. Instead the onus becomes on the application to deal with the problem themselves.

How have Oracle handled this? Eventually, by getting into the Linux Distribution business itself, with Oracle Unbreakable Linux. By releasing a complete OS build, they can coordinate OS and application releases, they can fix their version of the OS to handle problems that surface in Oracle's applications -on a timetable that works for them. They also get to handle Oracle hardware support in a timely manner, and charge support revenue from users.
 
That works -at a cost. By forking RedHat Linux, Oracle have taken on all the maintenance and testing costs themselves.

The amount that Oracles charge has to cover those costs, or the quality of the Oracle fork of Linux degrades relative to the reference points of RHEL and Debian.

For Oracle, or the combined OS+11g+exadata deal has enough margins in the database that they can come up with a price is was less than ({HP | Dell}-RHEL-Oracle11g), and so presumably those costs can be covered. What's not clear is this: did Oracle get into the business of selling a supported Linux because they saw money in it, or because they concluded that their hardware and database products effectively mandated it?


Other companies getting into the business of redistributing Hadoop-derived products to customers who are paying those companies in the expectation of support are going to have start thinking about this.

If you have just sold something that has some Hadoop JARs in it -code that the customer depends on- and they have a problem, how are you going to fix it?

Here are some strategies:

1. Hope it won't be a problem. Take the Apache artifacts, ship as is. It is, in the opinions of myself and my Hortonworks colleagues, production ready. Push customers with problems to issues.apache.org, forward them yourself. You could do the same with CDH, which in the opinions of my friends at Cloudera, also production ready.Do that, and issues on Apache JIRA will be ignored unless you can replicate them on the ASF artefacts.
2. Build your own expertise: this takes time, and while that happens you aren't in a position to field support calls. If you make your own releases, you end up needing your own test infrastructure, QA'ing it, and tracking the changes in hadoop trunk and branch-1.
3. Partner with the experts: work with people who have in-depth understanding of the code, it's history, why decisions were made and experience in cutting production scale releases suitable for use in web companies and enterprises. That means Hortonworks and Cloudera. Many of the enterprise vendors do this, because they've realised it was the best option.

The web companies, the early adopters went for #1 and ended up with #2: build your own expertise. This is effectively what I did in my HPLabs work on dynamic in-cloud Hadoop. You can see my journeys through the source -while working on big things, little things crop up, especially problems related to networking in a virtual world, configuration in a dynamically configured space, and recovery/sync problems that my service model discovered. I still know my way through a fraction of the code, but every project I work on builds up my understanding, and contributes stuff back to the core, including things like better specifications of the filesystem API's semantics, and the tests to go with it. 

That trail of JIRAs related to my work shows up something else: if you are delving deep into Hadoop, your reading of the code alone should be enough to get you filing bugs against minor issues, niggles, potential synchronization, cleanup or robustness problems. If you are pushing the envelope in what Hadoop can do: bigger issues.

We are starting to see some involvement in hadoop-core from Intel, though apart from the encryption contribs, it still appears to be at an initial state -though Andrew Purtell has long been busy in HBase. We do see a lot activity from Junping Du of VMWare -not just the topology work, but other big virtualisation features, and the day-to-day niggles and test problems you get working with trunk. Conclusion: at least one person in VMWare is full time on Hadoop. Which is great: the more bugs that get reported, the more patches, the better Hadoop becomes. Participating in the core code development project develops your expertise while ensuring that the Apache (hence Hortonworks and Cloudera) artifacts meet your needs.

Are there other contributors from EMC? Intel? I have no idea. You can't tell from gmail & ymail addresses alone; you'd have to deanonymize them by going via LinkedIn. That's not just name match; you can use the LI "find your contacts" scanner to go through those people's email addresses and reverse lookup their names. Same for twitter. I may just do that for a nice little article on "practical deanonymization".

In the meantime, whenever someone comes to you with a product containing the Apache Hadoop stack, say "if there is a problem in the Hadoop JARs - how are you going to fix it?"



[Artwork: See no evil by Inkie, co-organiser of the See No Evil event. Clearly painted with the aid of a cherry picker]

Followup: where can we do interesting things at low-levels

I managed to offend Andrew Purtell of Intel in my last post, so to make up here's some issues why Hadoop benefits from his work




Hardware is changing, CPU arch, memory layouts, cross-core synchronization, instructions built in the CPU. For efficient code we need everything from minimal branch misprediction to things that cut down core operations -especially decompression, checksums, encryption.

That's why the amount of native code in Hadoop is only going to increase -and that's going to take more than just skill to write -it takes the work to identify the problems and bottlenecks in the first place.


Java gets in the way here. You don't know the layout of a java class in memory, so it's near impossible to design cache-efficient designs, pulling in a class on a single cache line, avoiding false sharing within a struct. Even java's volatile opcode forces in a synchronisation barrier -making it much more expensive than C/C++ volatile. It's memory manager didn't go NUMA-aware until Java7 -it's been lagging hardware, but openJDK may speed things up there. Except now there's the problem of testing Hadoop on trunk builds of openJDK.

Looking forward, the end of HDDs is inevitable, but before then, mixed SSD and HDD will be the trend -and HDFS has to use that, somehow deciding where to put data, and knowing where it is.

If you are scheduling an MR job, and you have fast 10GbE networking, then the job placement problem becomes less of "where is there a slot on any of the three server with the data" and more "which of my 3 replicas are in SSD" -then doing work on or near that server, as things will complete that much faster.

And to have some storage of replicas across tiers will need HDFS knowing about the options, and making decisions. Those decisions will be hard, and you'll need something like a rebalancer in each host, moving cold data out of the SSD, so leaving space for warm data. Unless the SSD is actually used for write-through data, in which case the server you wrote two now has two copies, one on SSD, one on HDD. That may be a viable layout for two of the replicae. With P(SSD-fail) << P(HDD fail), you may even consider having more two-copy blocks, though there you would want them on separate boxes.

Other fun areas are OS integration, the underlying filesystem and networking stack. If you look at how today's servers & OSes are tuned, its towards things like databases. In a world where it's many-server designs, parallel operations across a cluster, things could be different

So yes: lots of areas to play in here, all welcome. Especially with tests.

[Photo: Jamaica Street. Centre looks like it is by Paris]

why you should vote for "Hadoop: Embracing Future Hardware"

At some point in the next 10-15 years, the last "rotating iron" hard disk will be made.

That's a profound thought. Admittedly, I may get the date wrong, but the point remains. Just as the CRT, the floppy drive and the CD has gone away, hard disks will become a rarity.

Who cares? Those of us building the future Hadoop platforms do.





GFS& MapReduce, Hadoop HDFS and its MR Engine, are all designed to take advantage of "commodity hardware". That means rather than pay for top of the line Itanium, PowerPC or Sparc servers running a Sysv-derived Unix, they use servers built from x86 parts running Linux. This is not because of any ideological support of the x86 architecture: nobody who has ever written x86 assembler or debugged win32 C++ apps at that level will be fond of the x86. No, x86 parts were chosen as they were the servers with the most cost effective performance, a manageable power budget (compared to Itanium) and because people made servers with them on board.

And why are x86 parts so cost effective -even though they have so many millions of transistors Because Intel have managed to take the revenue from each generation of parts into funding the R&D work and new fabs needed for the next generation of CPU parts and the processes to manufacture them.

It is the mass consumer and corporate demand for PC desktops that has given us affordable high-performance x86 parts,

Even if the Xeon stuff doesn't work in the desktop, the fabs and the core design are shared -the volumes kept the cost down.

With the emergence of phones and tablets as the new consumer internet access point, sales of PC parts are flatlining, and may decrease in future. Our home PC is used as a store for photographs and  a device for a ten year old to play minecraft or -or to watch youtube videos of minecraft. He isn't committed to intel parts, and as for the photgraphs, well, 1TB of cloud storage isn't affordable -yet- but that may change. And when your phone can upload directly to facebook, why faff around downloading things to a local PC?

Even enterprise PCs are changing, they are called "laptops" and SSD storage is moving down from the "ultrabook" class of devices to becoming mainstream -at a guess within 3-5 years they'll be SSD everywhere.

The world of end user devices are changing -which is going to have implications for servers. We need to look at those trends and start planning ahead, not just to handle the "what happens when HDDs go away" problem, but "how can we make best use of these new parts in 18-24 months?

Which brings me round to the whole point of this article: my other talk is Hadoop: Embracing Future Hardware,

Vote for it. If not, you'll be taken by surprise when the future happens around you while you weren't looking.

[Photo: something from the harbourfest , 2008l]