December 10, 2023

Did a denial-of-service attack cause the stock-market "flash crash?"

On May 6, 2010, the stock market experienced a “flash crash”; the Dow plunged 998 points (most of which was in just a few minutes) before (mostly) recovering. Nobody was quite sure what caused it. An interesting theory from, based on extensive analysis of the actual electronic stock-quote traffic in the markets that day and other days, is that the flash crash was caused (perhaps inadvertently) by a kind of denial-of-service attack by a market participant. They write,

While analyzing HFT (High Frequency Trading) quote counts, we were shocked to find cases where one exchange was sending an extremely high number of quotes for one stock in a single second: as high as 5,000 quotes in 1 second! During May 6, there were hundreds of times that a single stock had over 1,000 quotes from one exchange in a single second. Even more disturbing, there doesn’t seem to be any economic justification for this.

They call this practice “quote stuffing”, and they present detailed graphs and statistics to back up their claim.

The consequence of “quote stuffing” is that prices on the New York Stock Exchange (NYSE), which bore the brunt of this bogus quote traffic, lagged behind prices on other exchanges. Thus, when the market started dropping, quotes on the NYSE were higher than on other exchanges, which caused a huge amount of inter-exchange arbitrage, perhaps exacerbating the crash.

Why would someone want to do quote stuffing? The authors write,

After thoughtful analysis, we can only think of one [reason]. Competition between HFT systems today has reached the point where microseconds matter. Any edge one has to process information faster than a competitor makes all the difference in this game. If you could generate a large number of quotes that your competitors have to process, but you can ignore since you generated them, you gain valuable processing time. This is an extremely disturbing development, because as more HFT systems start doing this, it is only a matter of time before quote-stuffing shuts down the entire market from congestion.

The authors propose a “50ms quote expiration rule” that they claim would eliminate quote-stuffing.

I am not an expert on finance, so I cannot completely evaluate whether this article makes sense. Perhaps it is in the category of “interesting if true, and interesting anyway”.

No Warrant Necessary to Seize Your Laptop

The U.S. Customs may search your laptop and copy your hard drive when you cross the border, according to their policy. They may do this even if they have no particularized suspicion of wrongdoing on your part. They claim that the Fourth Amendment protection against warrantless search and seizure does not apply. The Customs justifies this policy on the grounds that “examinations of documents and electronic devices are a crucial tool for detecting information concerning” all sorts of bad things, including terrorism, drug smuggling, contraband, and so on.

Historically the job of Customs was to control the flow of physical goods into the country, and their authority to search you for physical goods is well established. I am certainly not a constitutional lawyer, but to me a Customs exemption from Fourth Amendment restrictions is more clearly justified for physical contraband than for generalized searches of information.

The American Civil Liberties Union is gathering data about how this Customs enforcement policy works in practice, and they request your help. If you’ve had your laptop searched, or if you have altered your own practices to protect your data when crossing the border, staff attorney Catherine Crump would be interested in hearing about it.

Meanwhile, the ACLU has released a stack of documents they got by FOIA request.
The documents are here, and their spreadsheets analyzing the data are here. They would be quite interested to know what F-to-T readers make of these documents.

ACLU Queries for F-to-T readers:
If the answer to any of the questions below is yes, please briefly describe your experience and e-mail your response to laptopsearch at The ACLU promises confidentiality to anyone responding to this request.
(1) When entering or leaving the United States, has a U.S. official ever examined or browsed the contents of your laptop, PDA, cell phone, or other electronic device?

(2) When entering or leaving the United States, has a U.S. official ever detained your laptop, PDA, cell phone, or other electronic device?

(3) In light of the U.S. government’s policy of conducting suspicionless searches of laptops and other electronic devices, have you taken extra steps to safeguard your electronic information when traveling internationally, such as using encryption software or shipping a hard drive ahead to your destination?

(4) Has the U.S. government’s policy of conducting suspicionless searches of laptops and other electronic devices affected the frequency with which you travel internationally or your willingness to travel with information stored on electronic devices?

Intractability of Financial Derivatives

A new result by Princeton computer scientists and economists shows a striking application of computer science theory to the field of financial derivative design. The paper is Computational Complexity and Information Asymmetry in Financial Products by Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge. Although computation has long been used in the financial industry for program trading and “the thermodynamics of money”, this new paper applies an entirely different kind of computer science: Intractability Theory.

A financial derivative is a contract specifying a payoff calculated by some formula based on the yields or prices of a specific collection of underlying assets. Consider the securitization of debt: a CDO (collateralized debt obligation) is a security formed by packaging together hundreds of home mortgages. The CDO is supposedly safer than the individual mortgages, since it spreads the risk (not every mortgage is supposed to default at once). Furthermore, a CDO is usually divided into “senior tranches” which are guaranteed not to drop in value as long as the total defaults in the pool does not exceed some threshhold; and “junior tranches” that are supposed to bear all the risk.

Trading in derivatives brought down Lehman Brothers, AIG, and many other buyers, based on mistaken assumptions about the independence of the underlying asset prices; they underestimated the danger that many mortgages would all default at the same time. But the new paper shows that in addition to that kind of danger, risks can arise because a seller can deliberately construct a derivative with a booby trap hiding in plain sight.

It’s like encryption: it’s easy to construct an encrypted message (your browser does this all the time), but it’s hard to decrypt without knowing the key (we believe even the NSA doesn’t have the computational power to do it). Similarly, the new result shows that the seller can construct the CDO with a booby trap, but even Goldman Sachs won’t have enough computational power to analyze whether a trap is present.

The paper shows the example of a high-volume seller who builds 1000 CDOs from 1000 asset-classes of home mortages. Suppose the seller knows that a few of those asset classes are “lemons” that won’t pay off. The seller is supposed to randomly distribute the asset classes into the CDOs; this minimizes the risk for the buyer, because there’s only a small chance that any one CDO has more than a few lemons. But the seller can “tamper” with the CDOs by putting most of the lemons in just a few of the CDOs. This has an enormous effect on the senior tranches of those tampered CDOs.

In principle, an alert buyer can detect tampering even if he doesn’t know which asset classes are the lemons: he simply examines all 1000 CDOs and looks for a suspicious overrepresentation of some of the asset classes in some of the CDOs. What Arora et al. show is that is an NP-complete problem (“densest subgraph”). This problem is believed to be computationally intractable; thus, even the most alert buyer can’t have enough computational power to do the analysis.

Arora et al. show it’s even worse than that: even after the buyer has lost a lot of money (because enough mortgages defaulted to devalue his “senior tranche”), he can’t prove that that tampering occurred: he can’t prove that the distribution of lemons wasn’t random. This makes it hard to get recourse in court; it also makes it hard to regulate CDOs.

Intractability Theory forms the basis for several of the technologies discussed on Freedom-to-Tinker: cryptography, digital-rights management, watermarking, and others. Perhaps now financial policy is now another one.

Thoughtcrime Experiments

Cosmic rays can flip bits in memory cells or processor datapaths. Once upon a time, Sudhakar and I asked the question, “can an attacker exploit rare and random bit-flips to bypass a programming-language’s type protections and thereby break out of the Java sandbox?

Thoughtcrime Experiments

A recently published science-fiction anthology Thoughtcrime Experiments contains a story, “Single-Bit Error” inspired by our research paper. What if you could use cosmic-ray bit flips in neurons to bypass the “type protections” of human rationality?

In addition to 9 stories and 6 original illustrations, the anthology is interesting for another reason. It’s an experiment in do-it-yourself paying-the-artists high-editorial-standards open-source Creative-Commons print-on-demand publishing. Theorists like Yochai Benkler and others have explained that production costs attributable to communications and coordination have been reduced down into the noise by the Internet, and that this enables “peer production” that was not possible back in the 19th and 20th centuries. Now the Appendix to Thoughtcrime Experiments explains how to edit and produce your own anthology, complete with a sample publication contract.

It’s not all honey and roses, of course. The authors got paid, but the editors didn’t! The Appendix presents data on how many hours they spent “for free”. In addition, if you look closely, you’ll see that the way the authors got paid is that the editors spent their own money.

Still, part of the new theory of open-source peer-production asks questions like, “What motivates people to produce technical or artistic works? What mechanisms do they use to organize this work? What is the quality of the work produced, and how does it contribute to society? What are the legal frameworks that will encourage such work?” This anthology and its appendix provide an interesting datapoint for the theorists.

NJ Voting-machine Trial: Defense Witnesses

I’ve previously summarized my own testimony and other plaintiffs’ witnesses’ testimony in the New Jersey voting machines trial, Gusciora v. Corzine.

The defendant is the State of New Jersey (Governor and Secretary of State). The defense case comprised the following witnesses:

Defense witness James Clayton, the Ocean County voting machine warehouse supervisor, is a well-intentioned official who tries to have good procedures to secure the Ocean County voting machines. Still, it became apparent in his testimony that there are security gaps regarding transport of the machines, keys to the machines, and security at polling places before and after election day.

Richard Woodbridge is a patent attorney who has chaired the NJ Voting Machine Examination Committee for more than 20 years. It’s not clear why the defendants called him as a witness, because they conducted only a 15-minute direct examination in which he didn’t say much. On cross-examination he confirmed that his committee does not conduct an independent analysis of software and does not consult with any computer security experts.

Robert Giles, Director of Elections of the State of New Jersey, testified about experimenting with different forms of seals and locks that New Jersey might apply to its AVC Advantage voting machines. On cross examination, it became clear that there is no rhyme or reason in how the State is choosing seals and other security measures; that they’re not getting expert advice on these matters. Also he admitted that there are no statewide control or even supervision of the procedures that counties use to safeguard the voting machines, the results cartridges, keys, and so on. He confirmed that several counties use the cartridges as the official tally, in preference to paper printouts witnessed and signed (at the close of the polls) by election workers.

Edwin Smith testified as an expert witness for the State defendants. Mr. Smith is vice-president and part owner of Sequoia Voting Systems. He stands to gain financially depending on the verdict in this trial: NJ represents 20% of Sequoia’s market, and his bonuses depend on sales. Mr. Smith testified to rebut my testimony about fake Z80 processors. (Wayne Wolf, who testified for plaintiffs about fake Z80s, testified after Mr. Smith, as a rebuttal witness.) Even though Mr. Smith repeatedly referred to replacement of Z80s as “science fiction”, he then offered lengthy testimony about methods to try to detect fake Z80s. This gave credence to the fact that fraudulent CPUs are not only a possibility but a real threat.

Mr. Smith also confirmed that it is a security risk to connect WinEds computers (that prepare electronic ballot definitions and tabulate results) to the Internet, and that those counties in NJ that do so are making a mistake.

Paul Terwilliger testified as a witness for the defense. Mr. Terwilliger is a longtime employee and/or contractor for Sequoia, who has had primary responsibility over the development of the AVC Advantage for the last 15 years. Mr. Terwilliger admitted that in 2003 the WIPO found that he’d acted in bad faith by cybersquatting on the domain name at the request of Sequoia. Mr. Terwilliger testified that it is indeed possible to program an FPGA to make a “fake Z80” that cheats in elections. But, he said, there are some methods for detecting FPGAs installed on AVC Advantage voting machines instead of the legitimate (Some of these methods are impractical, others are ineffective, others are speculative; see Wayne Wolf’s report.) This testimony had the effect of underscoring the seriousness of the fake-Z80 threat.

Originally the defendants were going to rely on Professor Michael Shamos of Carnegie Mellon University as their only expert witness. But the Court never recognized him as an expert witness. The Court ruled that he could not testify about the security and accuracy of the AVC Advantage, because he had not offered an opinion about security and accuracy in his expert report or his deposition.

The Court did permit him to testify in general terms. He said that in real life, we have no proof that a “hacked election” has ever occurred; and that in real life, such a hack would somehow come to light. He offered no studies that support this claim.

Professor Shamos attempted to cast doubt in the Court’s mind about the need for software independence, and disparaging precinct-based optical scan voting (PCOS). But he offered no concrete examples and no studies regarding PCOS.

On many issues, Professor Shamos agreed with the plaintiffs’ expert: it’s straightforward to replace a ROM chip, plastic-strap seals provide only a veneer of protection, the transformed machine can cheat, and pre-election logic-and-accuracy testing would be ineffective in detecting the fraud. He does not dispute many of the bugs and user-interface design flaws that we found, and recommends that those should be fixed.

Professor Shamos admitted that he is alone among computer scientists in his support of paperless DREs. He tried to claim that other computer scientists such as Ted Selker, Douglas W. Jones, Joseph Lorenzo Hall also supported paperless DREs by saying they supported parallel testing–implying that those scientists would consider paperless DREs to be secure enough with parallel testing–but during cross-examination he backed off a bit from this claim. (In fact, as I testified in my rebuttal testimony, Drs. Jones and Hall both consider PCOS to have substantially stronger security, and to be substantially better overall, than DREs with parallel testing.)

Parallel testing is Professor Shamos’s proposed method to detect fraudulent software in electronic voting machines. In order to catch software that cheats only on election day, Professor Shamos proposes to cordon off a machine and cast a known list of test votes on it all day. He said that no state has ever implemented a satisfactory parallel testing protocol, however.

Summary of the defendant’s case

One of the plaintiffs’ most important claims–which they demonstrated on video to the Court–is that one can replace the firmware of the AVC Advantage voting machine with fraudulent firmware that changes votes before the polls close. No defense witness contradicted this. To the extent that the defense put up a case, it hinged on proposed methods for detecting such fraudulent firmware, or on proposed methods for slowing down the attack by putting tamper-evident seals in the way. On both of these issues, defense witnesses contradicted each other, and plaintiffs presented rebuttal witnesses.