Right now, it’s pretty obvious that I don’t believe in the conspiracy theories (at least, the ones in which the US government or one of its agencies “made it happen on purpose”). However, I am no great supporter of the present US administration, and my political leanings (if transposed to America) would be somewhere to the left of the Democratic Party. Why then am I inclined to give Bush and his aides the benefit of the doubt? Of course it’s their sheer ineptitude: one need only look at the prosecution of the Iraq war for a rich seam of evidence.

But that doesn’t explain why I am so viscerally affected by the conspiracy theories: after all, I might be an atheist on the balance of probabilities, but I have no problem with people who have religious faith.

I think part of it is cognitive dissonance: we are raised to trust the government, and the idea that a government could be responsible for an atrocity like 9/11 is utterly incompatible with that preconception. I’ve already rationalised away the conspiracy theories, but perhaps not everyone would do the same.

Let’s assume that Democrats are more likely to believe and perpetuate the 9/11 conspiracy theories; and that Republicans and independents are more likely to recoil from them. There are photos of conspiracy theorist banners at Obama rallies. This is perfect ammunition for the Republicans, who can associate the Democrats with their “lunatic fringe” and exploit the cognitive dissonance in their base and the independents.

Here’s a conspiracy theory for you: Karl Rove sowed the seeds for the “9/11 Truth” movement in a deliberate attempt to discredit the Democrats and make them unelectable in the near future. Or maybe just to distract everyone from the true scandals of the Bush administration: tens of thousands of dead civilians in Iraq, thousands of dead soldiers, domestic spying on US citizens, the erosion of habeas corpus, inaction over global warming and the near collapse of the economy.

There are plenty of things that we still don’t know about 9/11, and we should as a matter of course seek the truth. We should discover the real reasons that the buildings fell in order to apply the lessons learned to future construction. But in finding the truth, we must retain an open mind, and not resort to intellectual dishonesty or partisanship.

Let us consider a single event from 9/11: the collapse of 7 World Trade Center, a 47-storey skyscraper which stood across Vesey Street from the main World Trade Center site. It collapsed at 5:21pm that day, but, unlike 1 and 2 World Trade Center (the north and south towers, respectively), it was not struck by an aeroplane.

As yet, the official report on the collapse has not been published: the working hypothesis is that fire and/or debris caused a critical supporting column to fail, ultimately leading to the collapse of the entire building.

A widely held conspiracy theory is that the building was destroyed by controlled demolition.

At present, there is no definitive evidence that proves either hypothesis: why then should we prefer one over the other? The conspiracy hypothesis can be proven, but not disproven. Any “proof” of the official hypothesis can be probabilistic at best, as it will be based on simulated physics with limited precision and an inherent (albeit possibly small) uncertainty. And that uncertainty leaves the door open for the possibility that Larry Silverstein ordered the demolition, or that thermite was used to hide the typical hallmarks of a controlled demolition, amongst other possibilities.

On the other hand, you can disprove the official hypothesis in a simple manner. Simply find one person who was involved in the conspiracy to admit his involvement. This could be one of the cabal who planned the atrocity, one of the secret services who executed it, one of the demolition experts who planted the explosives in the building, one of the building workers who saw explosives being installed, one of the emergency services who ordered the building’s evacuation or one of the news media who apparently reported the collapse before it happened.

Conspiracies do happen, but they can only succeed when the number of participants is limited: otherwise human fallibility makes it vanishingly improbable that the whole endeavour can remain a secret. And that is why, unless somebody comes forward and claims responsibility or provides legally credible witness evidence, I cannot (and we should not) believe that 7 World Trade Center was destroyed in a controlled explosion.

D x.

I do try to be environmentally-conscious—a task which is somewhat undermined by my air miles balance—and using fewer carrier bags seems like a good start. So I was cheered to see that Marks & Spencer’s have started charging for bags (although the emotional blackmail handed down by the checkout assistants may prove even more effective).

However, I’m rarely so organised that I have a bag with me when I nip into M&S for a Chicken Tikka ready meal. “Do you need a bag?” Well, yes, I’m afraid so.

The choice that remains is between the 5p traditional poly bag, and the mighty 10p bag for life. Now I hope it will not be too bourgeois of me to say that the difference between having 5p, 10p or nothing at all is negligible. So I usually plump for the bag for life, with the added satisfaction that “this bag is for life, it’ll last forever, and I’m saving the environment.”

But as I survey the pile of unreused bags littering my bedroom, I can’t help but wonder at the real cost. These bags are bigger and sturdier than their cheaper counterparts: how much more oil do they require to manufacture, and how much longer do they take to biodegrade?

Is it perhaps to time to increase greatly the charge for bags? If a bag cost £1, I’d make damn sure that I remembered to bring one with me….

I also found some notes I wrote for a couple of websites that, sadly, never saw the light of day. One was an elaborate satire on my high school, let down somewhat by the sophomoric title “Willywood“. The other was for a pseudonymous blog intended to have been published during my time in Guildford. I had developed “Bob” as somewhat affected and prolix character, who is aghast to find himself living in squalor in the south-east of England’s dullest dormitory town. I feel compelled to quote from the prologue:

Like two-thirds of a well-written American sitcome, two storylines intertwine to explain why I am here, writing this.

I’ll dispense with the Big Band-to-present montage that sat so awkwardly in the otherwise excellent Charlie Kaufman-penned Adaptation, and simply say that I got a job in Guildford.

I figured that I would stay at the University of Surrey. They clearly don’t value ten weeks’ rent, and wouldn’t accommodate me beyond late August.

I figured that I would ask my employer – with its established placement scheme – for some help. They sent an out-of-date brochure for B&Bs.

I figured that I would visit Guildford and look round at rooms for rent. In all, I saw three. I plumped for the least bad.

---

Unbeknownst to me, Mick and Kylie had let all three rooms in their 1970’s mid-terrace house. To celebrate the deal, they took the new tenants for a night out in Guildford. Words were spoken, things turned source, Kylie got in a fight with one of them, Mick weighed in to defend her honour, and an advert was placed the next day – Three rooms to let.

This I learned on my first night in the house, as they took me for a night out in Guildford.

I’d kind-of like to see where I might have taken this: there were plenty of horrifying anecdotes about that summer. How far away it seems now….

“I think that’s my bag,” he said.

“I’m fairly sure it’s not.”

“Does it have Turkish Delight in it?”

“Well, yes….”

Though these rivalries have existed for years, the internet has given them a new lease of life, in the hands of pure, unabashed saddos. Usenet has been the site of a proxy war, pitting Glasgow Airport against its rival in Edinburgh. The revision history for the Glasgow article on Wikipedia shows frequent changes in the population column, as well as the recent deletion of the comment, “Glasgow is the largest city in Scotland and all the more mysteriously is not the capital. Edinburh the second largest city in Scotland is the capital.” I can even remember reading one message board post where the author had counted the number of A-roads in each city and concluded that, having more, Glasgow was the more important.
In the interests of full disclosure, I must admit that I did once subscribe to both alt.airports.uk.glasgow and the edit feed for the city’s Wikipedia article. But having lived first in Edinburgh, now in England, I’ve become more laid back in my civic pride. Until today, that is.

A BBC news article reported on fears during the Cold War that a nuclear strike would have a grave effect on the nation’s tea supply. It mentioned that, for the purposes of planning:

the Ministry of Food listed London, Birmingham, Merseyside, Manchester and Clydeside [Glasgow] as H-bomb targets.

Tyneside, Teesside, Leeds, Sheffield, Hull, Derby, Purfleet in Essex, Southampton, Portsmouth, Bristol, Plymouth, Cardiff, Coventry and Belfast were named as A-bomb targets.

And all I could think was, ‘Ha, take that, Edinburgh….’

I am a little worried, however. Like just about everyone to whom I’ve talked, I’m hoping for a Democrat in the White House next year, and I’ve been following the primaries intently. But some of the recent pronouncements on trade have troubled me a little. So I’m hoping that, by writing something so naïve and ill-informed as this, someone will come out of the woodwork and tell me where I’m going wrong. Okay, here goes.

Let’s start by assuming that we’re all liberals. We probably want Barack Obama to be the next president, but maybe we’d rather it was Hilary Clinton. Either way, for the purpose of this discussion, it doesn’t matter.

We want things to be better for people in developing countries. To a first approximation, this could mean raising the standard of living in these countries by alleviating poverty. One way of doing this would be to spend more money in these countries. (Is this not why we’re all drinking fair-trade coffee, and eating fair-trade chocolate? Actually, scratch that, as I’m not convinced that the fair-trade movement doesn’t suffer from the exact same problems as what I’m about to describe. And sorry for the double-negative there.)

We are more likely to spend money in a country if we have free trade with that country, than if prices for goods from that country are inflated by duties or tariffs. We ensure free (or, perhaps more accurately, “freer”) trade by making free trade agreements with other countries.

So it’s heartening that, sometimes at least, both Obama [1] and Clinton [2] have supported NAFTA, which enables free trade between the US, Canada and Mexico.

Except, there’s a problem: free trade can cost jobs, especially manufacturing jobs in countries where the standard of living is so high that it is uneconomical to pay workers a living wage, when the same output could be obtained at a fraction of the price from one of our trading partners.

Especially jobs in traditionally blue-collar states like Ohio, where voters go to the polls today. And, therefore, both Clinton [3] and Obama [4] have attacked the other for supporting NAFTA, at the expense of American jobs.

So I have three questions:

• Which of the above assumptions is incorrect?
• I’d like to believe in Obama’s message of hope and change, but does this change stop at US border?
• If, as is now being reported, at least one of the candidates is engaging in disingenuous political posturing when making these statements [1] (and I’d be surprised if his opponent wasn’t also doing the same), then why should we believe in the rest of the rhetoric that goes along with it?

Now, I’m not an idealist, but I don’t particularly enjoy being cynical. Indeed, I hope I’ve made a mistake somewhere above, and someone will come along and correct me. However, it seems that, in an election that will probably be won on the strength of aspirational oratory, we should be especially critical of what is said.

Storage

DejaView: A Personal Virtual Computer Recorder

• The MEMEX Vision: We lack tools to store all of our books, records and communications quickly and with great flexibility. (Vannevar Bush.) We need to archive, search, view and manipulate what we have seen. Web/desktop search is inadequate: no record of what we have seen but not saved.
• DejaView: PVCR that provides complete, transparent, fast recording of the desktop computing experience. Tivo for the desktop. Records display like a video (playback, browse, ff, rw); and text and context to use as an index.
• Display recording: transparent, efficient and full-fidelity. Uses a virtual display driver that can redirect the display anywhere: to the user (on the screen) and to persistent storage. Has a standard device interface, intercepting updates at the low level and logs all display updates.
• Text/context recording: naïve approach would be do to OCR on the framebuffer, which is too slow and inaccurate. Instead leverage accessibility infrastructure (screen reader technology), which is integrated in most standard GUI toolkits. Also provides useful contextual information: name/type of application, window in focus, special properties (e.g. menu text).
• Execution recording: be able to revive execution state at any time, including the entire desktop session, not just a single process, and it needs to be fast enough to save frequently without degrading user experience. Use a virtual execution environment that decouples the desktop from the underlying OS by interposing on the syscall API. Only saves the desktop state and not the entire OS, which cuts down on the size of the checkpoint. Requires some downtime for the application during saving and snapshotting the filesystem, which must be optimised for interactivity. Checkpoint rate must be limited to make the overhead manageable. Also avoid taking pointless checkpoints (like when the desktop clock changes). A checkpoint per second is sufficient granularity.
• On revival, use UnionFS to put a CoW R/W layer on top of the R/O checkpointed file system. Can therefore fork history.
• Evaluation: based on real implementation - overhead, impact on interactivity and storage requirements; and access to data (latency etc.). Ran a bunch of benchmarks, based on normal workloads, like web browsing, video playback, catting a large file to screen, doing a kernel build, or something in Matlab. Also evaluated based on real desktop usage by grad students.
• Little overhead for display or execution recording; 100% overhead for text recording; 125% for full recording when web browsing (due to a bug in Firefox’s accessibility). All other use cases have much less overhead. Checkpoint latency: 5ms to 22ms downtime; total checkpoint time from 80 to 200ms. Storage growth is very low for the real usage scenario (lower than a PVR with equivalent display resolution). Browse and search latency no more than 200ms, which is good enough for interactive use. Playback speedup about 200x for real usage. Session revive takes 1.5 to just over 4s.

Improving File System Reliability with I/O Shepherding

• Storage systems are becoming complex, which can lead to complex failures. Want to manage disk and individual block failures. Addressed by checksumming, parity, mirroring, versioning, etc. However, these techniques are insufficient, and poorly understood (unlike performance and consistency). There is no good strategy in commodity FSs, only coarse-grained policies.
• Reliability treatments are diffuse and inflexible. Different apps require different policies (e.g. desktop workload versus web servers).
• I/O shepherd: localised, flexible policies for different types of storage. e.g. Mirroring for archival data, checksumming for scientific data, or different levels of protection based on the quality of the drive. These policies can be composed.
• I/O shepherding layer interposed between the FS and the disk subsystem. Includes >=1 policy tables, linking to policy code, policy primitives and policy metadata.
• Policy table: for specifying policies. Different kinds of block types and volumes, and levels of reliability and importance. So we have a write policy and read policy for each block type (like a function pointer); and a policy table for each volume (or mount point?).
• Policy metadata: need remapping, mirroring and sanity checking. Must be integrated with the FS. Also need I/O Shepherd Maps, to identify e.g. mirror locations.
• Primitives and Code: want to make reliability management simple. Primitives like “Checksum”, “Parity”, “Sanity Check”, “Allocate Near”, “Allocate Far”. These are then composed into a full policy, in the policy code.
• Challenge is to keep the new data and metadata consistent in the presence of crashes. Need consistency management.
• CrookFS: ext3 with shepherding capabilities. 900LOC changes to the OS, and 3500LOC for the shepherding infrastructure. Small overhead. Integrates reliability policy with journalling: execute policies during checkpoint.
• However, we can’t run e.g. remapping during checkpointing, because the checkpoint might fail, leaving us in an inconsistent state. If we keep the remap table in memory, the remap succeeds, but the program crashes before we can sync the table, we have the disk in an inconsistent state. At present, there is no consistency for any checkpoint recovery that changes state. Consistent reliability with the current journalling system is impossible!
• Thus we need “chained transactions”, which says that only after a chained transaction (updating the remap table) can the previous transaction (doing the remapping) be released. This fixes the flaw in journalling. It is repeatable across crashes, as long as we have idempotent policies.
• Evaluation: [see the paper].

Generalized File System Dependencies

• A new architecture for constructing file systems, using the “generalised dependency abstraction”.
• e.g. for consistency, we must keep FS consistent after every write, by, e.g. journalling. However must tradeoff durability features against performance. A file system must pick one tradeoff, but why can it not be extensible? This is difficult because it’s difficult to implement, complicated due to caches, and because correctness must be maintained.
• What is a simple, general mechanism for implementing any consistency model? The “patch” abstraction in their implementation, Featherstitch.
• Featherstitch contributions: the patch and patchgroup abstractions (explicit write-before abstractions, and FS-agnostic). Replaces Linux’s FS and buffer cache layer with implementations of ext2 and UFS. Journalling, WAFL and soft updates implemented just by using patch arrangements.
• Patches: a disk data change and any dependencies it has on other disk data changes. Includes some undo data. The dependency says which data must be written by which others. Benefits of this are to separate write-before specification and enforcement, and makes these relationships explicit. Inspired by soft updates, but don’t enforce a particular FS and consistency model.
• Example of rename: involves adding a directory entry and removing the old one. So we could write the source with the removed entry, then write the new entry. But what if we crash in between?
• Soft updates: inc ref count for the file inode, then add the new dirent, then remove the old dirent, then dec the ref count. However, this has a cyclic dependency for block updates. But, in patches, this is not a cycle. So we can do the increment patch, then do the other patches, with no cycle.
• Also showed how this would be done with journalling and WAFL: somewhat more complicated.
• Patchgroups: arise from application-defined consistency requirements. Commonly just syscall to the buffer cache (fsync, sync), or depend on the underlying FS. Instead, the patch interface is extended to user space, using patchgroups, which enables the specification of write-before requirements between syscalls. Can make things more efficient by not doing a bunch of syncs.
• Patch optimisations: massive dependency graph between patches even when allocating a few blocks for a new file, and so patches must have a lightning-fast implementation. Main primary overhead is unused undo data (150% overhead on some benchmarks). How do we detect where this is unused? Theorem is that undo data is only necessary when there are block-level cycles. So we should specify all dependencies when creating a patch.
• Next: the patch data structures take a large amount of memory. Therefore try to merge them, i.e. if they are on the same block (hard patch merging) and when they overlap. There are several other optimisations in the paper!
• Evaluation: measure optimisation effectiveness, compare with ext2 and ext3, check consistency, and run a benchmark (UW IMAP).
• The optimisations are successful in reducing the number of patches, system time and undo data overhead.
• Comparison with Linux: Featherstitch is between 19 and 26% slower at the PostMark benchmark. It’s faster on other benchmarks, where differences in the block allocation strategy outweigh the overhead.
• Consistency correctness: under random crashes, is the FS consistent. Works on Soft updates, Journalling as expected.
• Benchmark: moving 1000 messages from one IMAP folder to another. Patchgroups are much faster than using fsync.

Operating System Security

Information Flow Control For Standard OS Abstractions

• Problem: vulnerabilities in websites can lead to exploits. Solution: decentralised information flow control (DIFC). Example: admin wants to secure web app that handles secret and non-secret data. Use a “declassifier” which decides who gets to see what data. User authenticates to the declassifier then passes all requests through it. Even a bug in the webapp cannot leak data, because the declassifier makes the final decision on who can see what. So why is nobody using this, if it’s so good?
• Too hard to write the declassifier, requires smart people to develop all aspects of the system. Label systems are complex. Programming with DIFC can lead to unexpected behaviour. And it prevents the reuse of existing code, such as commodity operating systems.
• Unexpected behaviour: unreliable communication between two processes of different security types; mysterious failures when a secret process elevates the security of another process, and therefore prevents it from continuing with a task such as writing to an unsecure file (so that it can’t leak data from the secret process).
• Solution: Flume to solve DIFC problems (user-level DIFC on Linux with a simple label system, and glue between Unix API and labels). Then develop an application and evaluate it. Goal: want to be able to install this on existing machines using a apt-get.
• Uses system call delegation which forwards system calls to a user-level Flume reference monitor.
• Three process classes: confined (all syscalls go through refmon), Flume-oblivious (with no access to secret data), and unconfined/mediators (a mix of the two).
• Simple label system: each process gets a secrecy label which summarises the categories of data that a process is assumed to have seen. (e.g. Financial Documents, HR Documents.) Single category is a tag; set of tags is a label. Any process can add any tag to its label, but it cannot remove it without special privileges. A process can create a new tag, and is given the ability to declassify it (and hence remove it from its secrecy label).
• Communication rule: process p can send to q if p’s label is a subset of q’s label.
• Endpoints: intermediaries between processes for communication (per file-descriptor?), which can be labelled independently from the processes, and which declassify data. This is only possible if the owning process is able to declassify a tag in the secrecy label of the endpoint (better specified in set notation). A process can have many endpoints. This addresses some of the mysterious failures by eagerly revealing errors (which would violate the endpoint invariant).
• Example application is the Python-based MoinMoin wiki (100KLOC). 43 instances of the same check to see if the current user is able to access a bit of data, which have led to bugs, and plugins further complicate this. Instead add a 1KLOC declassifier. TCB is server + declassifier. Untrusted code is the Wiki plus any plugins.
• Apache is Flume-oblivious. Declassifier is a mediator. MoinMoin is confined, i.e. must syscall through the refmon.
• Results: Flume allows the adoption of existing Unix software: just 1% of MoinMoin had to be changed (no change in Python interpreter or Apache). By using Flume, two ACL bypass bugs were solved automatically. Performance is within a factor of 2.
• Limitations: bigger TCB than HiStar or Asbestos (Linux stack + 22KLOC refmon). Disk quotas are a covert channel.
• Q: On the example showing how endpoints are made, and secrecy labels may be changed, what if a malicious plugin attempts to perform declassification? This isn’t a problem, because, if the secrecy were critical to other applications, it wouldn’t be able to declassify the tag (because the tag would have been created by another application). Untrusted software would not have the elevated privilege to declassify tags.
• Q: Can the described policies be implemented inside SELinux? For a single application, probably yes, but the policies would become complex if it were possible to add applications to the change. Fluke simplifies system administration and transfers these decisions to the content provider.

SecVisor: A Tiny Hypervisor to Provide Lifetime Kernel Code Integrity for Commodity OSes

• Kernel rootkits: malware inserted in OS kernels to avoid detection by user-level scanners. Becoming increasingly common in the wild. DMA-based attacks are becoming common. Current (user-space) security tools are insufficient because they assume kernel integrity, and cannot find all attacks (as they are detection-based).
• Aim: a hypervisor that prevents injected code from executing at kernel privilege. Permit only user-approved code to execute a kernel privilege, based on a user-specified approval policy. Goals: security and ease of porting (not performance).
• ~1100LOC hypervisor, that operates at a ring below the kernel, but doesn’t attempt to do anything with hardware. Enforces approved code execution in kernel mode, which holds over system lifetime.
• Assumes: attacker can perform all attacks except HW attacks against CPU and memory. Can modify memory contents, perform DMA writes and modify system firmware. Can also have knowledge of 0-day kernel exploits. Single CPU with SVM or VT. Executed in 32-bit mode without the use of self-modifying code. No vulnerabilities in SecVisor (going to formally verify that).
• Require: constrained instruction pointer, which should be within approved code regions whenever CPU is in kernel mode. Approved code regions must be immutable, and so cannot be modified by an attacker.
• Constrained IP: kernel mode entry should set IP to being within approved regions. IP must remain within approved regions as long as we stay in kernel mode. Each kernel mode exit should set the CPU privilege level to user mode.
• Kernel Entry: exception/interrupt happens, looks up handler in the interrupt vector, and jumps to that IP in kernel mode. So all entries in the vector must point to approved code.
• During execution: place write XOR execute protection over kernel memory. But the problem is that the kernel and application share the same address space, so what if the attacker attempts to jump to user-space code, maybe by performing a buffer overrun. Solution: mark all application memory as non-executable (NX) on kernel entry.
• Intercepting user-to-kernel switch: all CPU entry pointers point to approved code; mark approved code regions as NX during user mode execution; all user-to-kernel switches raise exceptions.
• Kernel exit: intercept all kernel-to-user switches by using the exception that is raised by trying to execute NX code in user space after the switch back to user space.
• Immutable approved code: memory may be written by software executing on CPU or by DMA writes by peripherals. Approved code must be marked read-only. IOMMU protects from DMA writes.
• Implementation of memory protection: set protection independent of OS, using shadow (or nested) page tables. DMA exclusion vector to protect approved code.
• [I don’t think I need to include the explanation of shadow page tables.]
• Shadow PT is used to set memory protections. Approved code regions are set read-only in the SPT, and DEV prevents DMA writes. We also need to prevent aliasing of pages that are in the approved regions to non-approved VAs.
• Check entry pointers to ensure they contain VAs of approved code. GDT, LDT and IDT must be protected by shadowing these (to protect them from DMA writes).
• Overhead from intercepting all switches, and the shadow PT synchronisation and kernel PT checks. I/O-intensive workloads will perform poorly.
• Specint benchmarks show that SecVisor is about 2 to 5% slower than Xen (except for the gcc test, where it is much slower). Some optimisation has been done in the latest version.
• Q: Many past kernel exploits change the uid of user processes to overwrite kernel memory; does SecVisor address this? It doesn’t protect the integrity of kernel data structures. This is future work.
• Q: Performance effect of nested page tables? Shadow overhead goes away, but you still have to check and protect the kernel page tables.
• Q: Knowing everything you know about the system, how would you attack it as an intruder? Try to attack the TCB, but it is very small, so we don’t expect that this will be a problem.
• Q: Deal with loadable modules? Paper discusses this: you could have a hash-based approval policy, and SecVisor performs code relocation on behalf of the kernel.
• Q: How to protect the stable storage off which SecVisor is loaded? Use skinit, along with trusted computing techniques.

Secure Virtual Architecture: A Safe Execution Environment for Commodity Operating Systems

• Safe execution environment: such as that provided by Java or C#. Array indexing within bounds, no use of uninitialised variables, type safe operations, no dangling pointers, control flow follows semantics, etc.
• Commodity OSs do not use these kind of languages.
• Using as secure exec env would provide security, novel design opportunities and the ability to develop new solutions to higher-level security challenges (such as information flow policies, for example).
• Secure virtual architecture: interpose a compiler-based VM between a commodity OS and hardware. The VM provides a virtual instruction set architecture.
• Contributions: a compiler-based VM that can host a commodity OS. First to provide security guarantees for a complete commodity OS.
• Safety-checking compiler: similar to a C compiler which translates C into the virtual ISA (application level). Generates bytecode rather than native code. Bytecode has a type system which enables alias analysis in the VM.
• VM contains a safety verifier (which ensures that the compiler has done the right thing; may insert runtime checks), native code generator, and OS and memory safety runtime libraries. The compiler is outside the TCB; only the verifier and code generator are inside.
• Virtual ISA based on LLVM. Added OS-neutral operations (SVA-OS) that remove difficult to analyze assembly code and encapsulates privileged operations. Porting to SVA-OS is like porting to a new arch.
• Goals: maximise safety guarantees, minimise reliance on OS correctness, minimise changes to the kernel, and retain original kernel memory allocators.
• Guarantees: just like Java or C#, but type safety only for a subset of objects (due to the use of C code), and dangling pointers are harmless (rather than never used). These limitations do no compromise the other guarantees.
• Checks: load/store, bounds, illegal free and indirect call. Transforms: stack to heap promotion to deal with dangling pointers, and initialising memory. Need to track object bounds: use object lookups. Naïvely, the security verifier would add code to register all allocations in the VM metadata. All uses of these objects would have to follow a lookup to see if the access is within bounds. Can improve this by alias analysis, which groups objects into logical partitions, reducing overhead from between 400 and 1100% to between 10 and 30%.
• Implementation: ported Linux to the SVA ISA, compiled using LLVM. SVA-OS is a runtime library linked into the kernel. Guarantees safety of everything apart from the kernel memory management code and [blink and you’ll miss it, see the paper]. Around 5KLOC had to be changed in Linux.
• Memory safety overhead is less than 59% (for a web server benchmark). Latency is bad with many small transfers. 80% of exploits caught (the non-caught one was in a library that isn’t currently ported to the VM).
• Several performance improvements are possible, by changing the code, using smarter checks and smarter static analysis.
• Q: To what extent does the analysis equate to type safety? Do not guarantee that pointers point to the correct object, but that it is a valid object.
• Q: Must the number of memory pools be statically allocated? No. What if memory pools are allocated at run-time? Even then, its use is statically identifiable.
• Q: Is the overhead really small enough to make this approach suitable for use today? Improving the overheads is future work.

And, with that, I’m off to Portland for an afternoon of shopping in a city where £1 buys $2.03, and there’s no sales tax. See you when I get back!

Software Robustness

Bouncer: Securing Software by Blocking Bad Input

• Filters block bad input before it is processed. Low overhead and no false positives. Programs can keep running even when under attack.
• Performs symbolic execution of programs to perform analysis and generate input filters. Works on machine code.
• Pre-condition slicing: compute a subsequence of trace instructions, executing which is sufficient to create a vulnerability. Find instruction with vulnerability (e.g. call to sprintf), then move backwards through the trace, adding the instructions on which the vulnerable instruction depends.
• Deployment in a distributed scenario. When an exploit is found, run Bouncer, calculate an improved filter, and deploy this. Or run centrally on a cluster to find exploits in parallel.
• Nirvana generates traces. Phoenix implements slicing.
• Evaluated against four real vulnerabilities (including the Slammer worm). Ran experiment for 24 hours.
• Filters have no false positives. Found perfect filters for two vulnerabilities. Some false negatives for two others.
• Throughput is much closer to 100% when using filters, compared to having to restart on each attack. Can still maintain 80% throughput with 18000 attack probes per second.

Triage: Diagnosing Production Run Failures at the User’s Site

• What to do with a production run failure (send error report)? At present, we just send a core dump, which takes a lot of manual effort to diagnose. At the same time, these failures cause damage to end users.
• Reproduction is hard, because user environment is unique. Furthermore, there are privacy concerns.
• Core dumps tell you what the failure is. Bug detection tells you about some errors. Diagnosis is a means of tracing back to the underlying fault, but existing tools are offline (e.g. requiring programmer input).
• To diagnose: (i) need information about the failure (fault, error, propagation tree), but off-site techniques don’t work on-site; (ii) need guidance about what to do next, the kind of analysis to perform, the interesting variables to investigate (but there is no programmer to do this, so decisions must be taken automatically); (iii) need to be able to test “what-ifs”, such as changing input and seeing what happens, but most techniques focus on replaying the same thing.
• Triage enables on-site diagnosis, using systems techniques to make offline analysis tools useful on-site, addressing the three challenges. It introduces a new technique called delta analysis. Tested in a human study with real programmers and real bugs.
• Uses checkpointing and re-execution to capture the bug. Allows replaying the failure repeatedly, using different analysis tools. Little overhead in the normal-run case. Checkpoints every 200ms, keeping 20 previous checkpoints, in memory to lower overhead.
• Uses a human-like “diagnosis protocol”. Repeated replay enables an incremental diagnosis. e.g. If the bug doesn’t always repeat, it may be a race condition.
• But the replay isn’t identical: it can either be deterministic (plain), loose (tolerating some variance, such as the introduction of analysis tools which change the syscalls) or wild (including potentially large variations, maybe changing input or the code itself). Delta analysis is similar to diffing a pair of (successful and failing) runs. Triage doesn’t need to be safe when it replays execution: it only cares about why the bug happens.
• Failure analysis variety of methods (bounds checking, taint analysis, symbolic execution, etc.) and delta generation (rearrange allocations, drop inputs, mutate inputs, drop code(!)).
• Delta analysis: compute the basic block (of code) vector (1 if executed, 0 if not), and subtract them. The two closest runs are diffed (finding the edit distance and shortest edit script). So a basic block that differs could for example be to return NULL, and it is then dereferenced.
• Human study: 15 programmers from faculty, researchers and grad students. Measured times to repair bugs with and without Triage. (People got core dumps, sample inputs, instructions for how to replicate, and access to debugging tools.) The evaluation didn’t expect the participants to work out how to replicate the bug, and set a maximum time.
• 47% time saving on diagnosing real bugs, significant with probability of null hypothesis < 0.01%.

/* iComment: Bugs or Bad Comments? */

• Many bugs are due to mismatches between the code and the programmer’s assumptions. Such as assuming that a lock is held when a piece of code is executed. Comments express these assumptions. 20% of Linux is comments (excluding blank lines and copyrights), but they are not utilised by compilers or bug detection tools.
• However, comments are imprecise, compared to code, and cannot be tested. Therefore they tend to become less reliable as software evolves. Nevertheless, they are easier to understand for programmers. So wrong comments are likely to mislead programmers. Difficult to infer assumptions from source code (but see the MUVI paper from yesterday).
• Mismatches indicate either bugs or bad comments. Challenge is to understand the natural language of comments. NLP techniques are not enough: POS tagging (97% accurate), chunking (90%) and semantic role labelling (70%). But they assume correct grammar, which comments don’t always have.
• Therefore, also use machine learning, staistics and program analysis (with NLP). 1832 rules extracted, detecting 60 new bugs or bad comments (19 of these confirmed). Looking at call and locking bugs only.
• Focus on the comments that contain rules (rather than explaining code), as these are more likely to be inconsistent with the code.
• Example rule: must be held before entering .
• Comment classifier is trained using a decision tree building algorithm. Some manual training is required (at least once per topic).
• Validated using Linux, Mozilla, Wine and Apache, looking at lock- and call-related topics. Overall, 60 mismatches, 33 (12 confirmed) bugs, 27 (7) bad comments and 38 false positives, from 1832 rules. Training accuracy is between 90 and 100% (for lock-related comments). Cross-software accuracy is between 78 and 90% (saves the amount of training).

Distributed Systems

Sinfonia: A New Paradigm for Building Scalable Distributed Systems

• The protocols in current distributed algorithms are complicated, error-prone, and often difficult to understand. We want to avoid such protocols. Focus is on data centre systems, with small and predictable latencies, and occasional crashes. Focus also on infrastructure applications, like cluster file systems, lock managers and communication services.
• Sinfonia is a data sharing service, comprising a set of memory nodes which each export a linear address space (no structure imposed). Protocol design becomes the easier problem of shared data structure design. Minitransactions are used to access the memory nodes.
• Minitranscations have ACID properties, balance power and efficiency. Reduce network round-trips, but are still flexible and easy to use. Semantics: perform a bunch of compare items (for equality over an address range), if all of these match then retrieve the read items and perform the write items. Execution of the transaction is piggybacked on the two-phase commit process, to minimise round-trips.
• Commit coordinator runs at the application, which may crash, so a new two-phase commit protocol was necessary. Based on all memory nodes logging a “yes” vote, rather than the coordinator logging a “commit” decision.
• Applications: sinfoniaFS (a cluster file system) and sinfoniaGCS (a group communication service - i.e. a chatroom with ordered notifications).
• sinfoniaFS performs as well as LinuxNFS in the Andrew benchmark. sinfoniaGCS scales better than Spread.

PeerReview: Practical Accountability for Distributed Systems

• Fault in a distributed system with distributed state can lead to incomplete information. In the general case, there could be multiple admins with different interests (and possible malicious intent).
• Many faults are not fail-stop but instead change behaviour of a node. Dealing with general faults is difficult, because of a lack of control over the system. How can faults be detected or the faulty nodes identified. Then how do you convince others that a node is faulty (or not faulty) and must be fixed.
• Real-world systems rely on accountability. e.g. signed receipts, double-entry bookkeeping and auditing. These can be used to detect, identify and convince about faults.
• A fault is when a node deviates from expected behaviour. We want a system that generates a proof of misbehaviour against a faulty node. Difficult if we consider a fault that affects only a node’s internal state (requires an online trusted probe at each node). So we focus on observable faults: those that causally affect a correct node, and don’t require a trusted component.
• Verifiable evidence: a proof of misbehaviour or a challenge that a faulty node cannot answer.
• Accountability: whenever a fault is observed by a correct node, the system eventually generates verifiable evidence against a faulty node.
• Implementation: as a library, PeerReview. Assumes that nodes modelled as a collection of deterministic state machines, with each node holding a reference implementation of all state machines. Also that correct nodes can eventually communicate and nodes can sign messages.
• All nodes log all inputs and outputs. Each log is audited periodically by witnesses (a set of nodes for each node). If misbehaviour is detected, evidence is generated and distributed to other nodes.
• Log entries form a hash chain to prevent forgery of a log. Keeping multiple logs or forking logs is prevented by checking the signed hashes to ensure that a single linear log is kept. Faults in a log are recognised by replaying the state machine with the known inputs and checking outputs against the log.
• PeerReview guarantees that faults will be detected and good nodes cannot be accused.
• Applicability: NFS server in the Linux kernel, overlay multicast, and P2P email system. Deals with small latency-sensitive requests, large transfers, and complex, large and decentralised systems.
• Dominant cost depends on the number of witnesses per node.
• Normal P2P email scheme scales as O(log n) with n being the number of nodes. PeerReview can scale O((log n)^2) if you accept a 99.999% probability of detecting faults. (100% accuracy is prohibitive (linear, I think)).

Dynamo: Amazon’s Highly Available Key-Value Store

• Amazon architecture: loosely coupled SOA, with stateful services that manage their own state. Requirements on latency, availability and scale.
• State management is the primary factory affecting scalability and availability. Data is only ever accessed by primary key, in self-describing blobs, so key-value is better than RDBMS (don’t need a query optimiser, triggers, etc.). RDBMS scale up, not out, and (strong, transactional) consistency is less important than availability.
• Dynamo requirements: always writable (accept writes during failures), e.g. to add an item to a shopping cart must always be possible; user-perceived consistency (so can’t be too weak on consistency); performance with latency in the 99.9th percentile; low cost; incremental scalability; and tunable knobs for cost, consistency, durability and latency. No production-ready systems met these requirements
• Replicated DHT with consistency management, using: consistent hashing, optimistic replication, sloppy quorum; anti-entropy mechanisms; and object versioning.
• DHT is similar to Chord, using MD5 as the hash function. Clique for routing between replicas. Each storage node given many locations on the ring for load-balancing. Trade-off between balancing load and keeping membership tables concise.
• Configurable for different scenarios e.g. consistent, durable, interactive user state; a high-performance read engine; or a distributed web cache.
• Able to meet a 500ms SLA on latency, for the implementation of a shopping cart.
• Drawbacks: no indefinite scaling, not appropriate if transactional semantics required, more challenging to program than using ACID properties.

System Maintenance

Staged Deployment in Mirage, an Integrated Software Upgrade Testing and Distribution System

• Typically test on a couple of vendor machines, then a bunch of beta tests in the outside world, but despite this, the software will still fail on user machines in the outside world (due to dependencies, odd configurations, etc.). Mirage enables vendors to cluster outside world machines in terms of the their configurations/environment, so as to ensure coverage of beta testing before public release (and hence improve reliability). This reduces “upgrade overhead”: the number of machines that fail.
• Environment must be identified and fingerprinted, before clustering. Then the order and speed of deployment must be chosen by the vendor.
• In a cluster, all machines “behave identically wrt an upgrade”. Benefit depends on quality of clustering and the quality of testing.
• Identification: instrument the application to determine the resources (libraries, config files, environment variables and dependent applications) that it uses during a normal run. Filter out noise (log files, temp files and data) based on heuristics and vendor-provided rules. A library becomes a (name, version, hash of binary) tuple. The hash is used in case there are different builds, for example.
• Tradeoff between low upgrade overhead (few failures) and fast deployment. Choice between deploying in parallel to many clusters (fast, but high overhead), or sequentially (slow, but low overhead). Fixing a problem for one environment might also fix it for another environment (benefit of serialisation).
• Evaluated the quality of clustering (identification and clustering), and staged deployment (the upgrade overhead and deployment speed).
• Accurate identification: between 200 and 850 environment resources (on firefox, apache, php and mysql), between 0 and 7 vendor rules, yielded 0 errors in any case.
• Accurate clustering: 21 different environments, with 2 distros of linux, PHP and Apache and various MySQL configurations. Yielded 0 misplaced machines within 15 clusters. Varying the fingerprinting granularity can vary the number of clusters.
• Controlling the tradeoff: simulation with 100,000 machines, 3 problems and 2 staging protocols. Upgrade overhead reduced very significantly, with, in the worst case, a 25% increase in deployment time.
• Studying “real machines” and deployments is the subject of future work.

AutoBash: Improving Configuration Management with Operating System Causality Analysis

• Current approach to configuration management is to ask friends, search online, read manual, try potential solutions. Frustrating, time consuming and tedious! Hard to undo a wrong solution or know if the problem was solved. A solution can cause new problems.
• AutoBash: tries many solutions at once, provides an undo capability, explains to the user how it solves a problem and automatically runs regression tests.
• When a problem is detected, there are two modes: Replay mode which automatically searches for a solution; and Observation mode which helps the user to fix the problem. All the time, there is a Health monitoring mode.
• Observation mode: a modified bash where user tries to fix a problem by typing a command then testing if the app works, then possibly undoing the command and rolling back the command, before trying again. Has “predicates” which test if an application functions correctly and returns true iff the test passes. Idea is for application to be shipped with a testsuite of predicates. Speculator (SOSP’05) is used to perform process-level speculative execution, and make predicate testing safe (undoable). Shell provides a rollback command, used in conjunction with the speculative execution, to undo the attempted command.
• Regression testing is handled by running all predicates in some database. This can be slow, however, so causality tracking is used to find which predicates might be affected by a change.
• Tracking causality: Output set of kernel objects that an action causally affects, and Input set of kernel objects on which a predicate causally depends. If the output set of an action and input set of a predicate intersect, then the predicate must be checked. The output set can be tracked by syscall tracing, and then trimmed by excluding temporary objects (such as processes, or temporary files). Similarly, this can be done to determine the input set of a predicate.
• Generating a causal explanation: the important actions are the ones whose output sets intersect with the input sets of the newly-passing predicates.
• Replay mode: assume that vendors ship “common solutions” with their software, so that these may be automatically tested (safely, using speculative execution) in the background, while the user gets on with work.
• Evaluation: overhead of speculative execution and effectiveness of causality analysis? Looked at CVS, GCC cross compiler and webserver. Created 10 bugs and 10 solutions.
• Very little overhead (non-significant) of speculative execution. Causality analysis almost halves the total replay time, with a slight increase in the predicate testing time.

Energy

Integrating Concurrency Control and Energy Management in Device Drivers

• Concentrating on wireless sensor networks. Concurrency of I/O operations are considered (synchronous versus asynchronous). Energy management is considered in terms of the necessary power state of devices to perform I/O.
• The more workload information the app can provide the scheduler, the less energy needs to be used.
• Hard to tell OS about application workloads: API extensions for hints to energy management. Done for CPU voltage scaling and disk spin-down. Sensor networks need a unique solution, however: harsh requirements, small power source, and need to run unattended for periods ranging from months to years. 1st generation OSs push all decisions to the applications.
• ICEM: a driver architecture that automatically manages energy, implemented in TinyOS 2. New concept of Power Locks: split-phase (asynchronous) locks with integrated energy and configuration management. Dedicated, shared and virtualised drivers and a component library for building them.v Energy efficiency is 98.4% of hand-tuned implementation. Also much easier to program.
• Case study on the TMote platform: three interfaces to six total devices. Logging application with producer, which writes sensor samples out to flash every 5 minutes, and a consumer that sends all samples from flash over the radio every 12 hours. Code complexity of hand-tuned implementation is very complex: need to order the power-on and -off of each different device. ICEM hides these calls, greatly simplifying the code.
• Split-phase I/O operations: single thread of control, where read() call is given a callback, readDone(), that allows the driver to poke the application when it is done. These can then be scheduled efficiently, because the driver has information about what has to be done before it considers switching the device off.
• Virtualised driver: only a functional interface. Assume multiple concurrent users, buffering requests for concurrency management, and managing energy by looking at pending requests. Such drivers have longer latencies, because the underlying device has to have synchronous access. Suitable for high-level hardware (like a block device?)
• Dedicated driver: functional and power control interfaces. A single user only with no concurrency control and explicit energy management. Suitable for low-level hardware.
• Shared driver: functional and lock interfaces. Multiple users, explicit concurrency control (using the lock), and implicit energy management based on pending requests.
• Power locks: hardware-specific configuration and power interfaces, and a lock interface. Talk to a dedicated driver. First, request access to the lock, which powers on the underlying device and configures it and calls back the application (split-phase). Other locking requests are queued after the current user. Power down only happens when all pending lock requests have been fulfilled and released.
• Arbiter: performs concurrency control and queuing/scheduling (FCFS and round-robin). Configurator: calls h/w-specific configuration interface on the dedicated driver. Power Manager: powers down device when it falls idle, and powers it back up when a new lock request comes in (with immediate and deferred policies).
• Evaluation: comparing hand-tuned, ICEM, optimal serial and worst-case serial orderings, in the sensor logging application described above. ICEM performance very close to hand-tuned, and better than both serial versions.
• ICEM overhead is 5.60% of total sampling energy. Node lifetime for ICEM is between 98.4% and 100% of the hand-tuned version, as the sampling period is increased.

VirtualPower: Coordinated Power Management in Virtualized Enterprise Systems

• Two key benefits of integrated power management: power savings are proportional to cost savings, and cooling capability is proportional to rack utilisation. Information and capabilities exported ACPI have led to application-specific power management policies. How do we do this in the context of virtualisation?
• Problems: what should be exposed? Are there issues with isolation? Are there power benefits arising from resource sharing? VPM can give a 34% power improvement.
• Data centres have a heterogeneous collection of platforms. Virtualisation should abstract this (e.g. because of migration), but this is tricky with different power characteristics in the underlying hardware. The workload stays the same, so we should virtualise the power management states: therefore we can have a consistent view of manageability across migrations.
• What about isolation? Disassociate changes to virtual state from the management of the physical state: front-ends in DomUs, back-end in Dom0, the latter of which manages the physical state. Notion of soft scaling which allows the possibility of “scaling” a virtual CPU, which enables consolidation of soft-scaled virtual resources. (Two soft-scaled VCPUs on a single full-power CPU, but you might be able to turn off another physical CPU, for example.)
• VPM rules in Dom0 which control the physical PM. Virtualisation layer policies are driven by VPM state requests from the VMs, which makes an implicit feedback loop. Might need some learning algorithms to derive rules.
• e.g. Dom1 changes VPx state via a hypercall and creates a VPM event (comprising the VM soft state, and a shadow state (the physical manifestation of the current soft state). This leads to a new set of shadow states being calculated.
• Workloads: tiered web service (RUBIS) (Linux on-demand gonvernor); transactional workload (select policy based on the transaction processing rate and the amount of slack); web service with quality of information metric (Travelport (Worldspan)) (policy based on the QoI and processing time of requests across different client classes).
• Complex analysis has up to 4% degradation on throughput. Seems to work with multiple VMs too. [Lots of fairly convincing graphs but I think it’ll be necessary to take a good look at the paper to judge what we’re actually being presented.]