· 9 years ago · Jan 25, 2017, 09:10 PM
1|=-----------------------------------------------------------------------=|
2|=---------------------=[ Cyber Grand Shellphish ]=----------------------=|
3|=-----------------------------------------------------------------------=|
4|=------------------------=[ Team Shellphish ]=--------------------------=|
5|=----------------------=[ team@shellphish.net ]=------------------------=|
6|=----------------=[ http://shellphish.net/cgc#team ]=-------------------=|
7|=-----------------------------------------------------------------------=|
8
9
10 #####
11 # # # # ##### ###### #####
12 # # # # # # # #
13 # # ##### ##### # #
14 # # # # # #####
15 # # # # # # # #
16 ##### # ##### ###### # #
17
18 #####
19 # # ##### ## # # #####
20 # # # # # ## # # #
21 # #### # # # # # # # # #
22 # # ##### ###### # # # # #
23 # # # # # # # ## # #
24 ##### # # # # # # #####
25
26 MM
27 . MM
28 = M
29 M MM
30 MM M
31 MM MM
32 ,M M
33 MMM MM+ MM MM M
34 MM MM MM MM MM MMMMD MMM
35 MM+ MM MM MM MM +M MM :M MM MMM:
36 MMMM MM MM MM MM MM MMD M. MM MMM M MMM
37 MMMMM =M~ MM MM MM MM MM M~MM MM ~MM MM MM
38 ,MMM OM MM MM MM MM MM M.MM MM MMM MMMMMM+NM MM MM
39 MMMMMMMMMM +MMMMMM MMMN MM MM MMMMMM MM MM MM MM MMO MM
40 MMMMMMMMMMMMM MMMMMM MMMN MM MM MMMMMN MMMMMM MM MMMMMMMMM MMMMMMM
41MMMM: MM MM MM MM NM: MM ?M MM MM MMM MMM MM MM
42,M MMM MM MM MM MM MM? MM ~MM ~M MM :MMMMMMMMM MM MMM
43 M M~MMMMMM MM~ MM MM MM MM NM+ MM MM NMM ~N MM
44 ,MMMMMMM8 MM MM :MN MM MM+ MMI NMM M
45 MMI MM MMM+ MM~ MMD~ MM
46
47
48
49|=-----------------------------------------------------------------------=|
50|=----------------------------=[ The Team ]=-----------------------------=|
51|=-----------------------------------------------------------------------=|
52|=---=[ zardus ]=-----=[ mike_pizza ]=---=[ anton00b ]=----=[ salls ]=---=|
53|=-----------------------------------------------------------------------=|
54|=---=[ fish ]=---------=[ nebhiros ]=---=[ cao ]=--------=[ donfos ]=---=|
55|=-----------------------------------------------------------------------=|
56|=---=[ hacopo ]=---------=[ nezorg ]=---=[ rhelmot ]=------=[ paul ]=---=|
57|=-----------------------------------------------------------------------=|
58|=----------------------------=[ zanardi ]=------------------------------=|
59|=-----------------------------------------------------------------------=|
60
61
62
63
64Hacking is often considered more than a skill. In popular culture, hackers
65are seen as wizards of sorts, artists with powers to access the
66inaccessible, or perform acts that seem impossible. Hacking, like art, has
67great people, who are recognized for their skills, but whose abilities
68cannot be captured or reproduced. In fact, a single great hacker in a team
69is better than a hundred mediocre ones, similar to as none of the paintings
70from a hundred mediocre artists can match a painting from van Gogh.
71
72Vulnerability analysis is the science of capturing and reproducing what
73some hackers do. Vulnerability analysis studies how one can reason, in a
74principled way, about finding and exploiting vulnerabilities in all types
75of software or hardware. By developing algorithms and tools to help humans
76identify flaws in software, researchers "codify" the knowledge that hackers
77use, in an organic way, to analyze systems and find their flaws. The
78resulting tools can then be used at scale, and composed to create new
79analysis systems.
80
81This scientific process has generated a number of useful tools, such as
82static analysis tools, fuzzers, and symbolic execution frameworks. However,
83these tools codify only a subset of the skills of a hacker, and they are
84still used only to augment the abilities of humans.
85
86One approach to push the codification of what human hackers do, is to take
87the hackers out of the equation. This is precisely what the DARPA Cyber
88Grand Challenge was set out to do.
89
90The DARPA Cyber Grand Challenge (CGC) was designed as a Capture The Flag
91(CTF) competition among autonomous systems without any humans being
92involved. During the competition, Cyber Reasoning Systems (CRSs) would find
93vulnerabilities in binaries, exploit them, and generate patches to protect
94them from attacks, without any human involvement at all.
95
96The separation between human and machine is key, as it forces the
97participants to codify, in algorithms, the techniques used for both attack
98and defense. Although the competition was only a first step toward
99capturing the art of hacking, it was an important one: for the first time,
100completely autonomous systems were hacking one another with code, and not
101human intuition, driving the discovery of flaws in complex software
102systems.
103
104
105Shellphish is a team that was founded by Professor Giovanni Vigna at UC
106Santa Barbara in 2005 to participate in the DEF CON CTF with his graduate
107students. Since then, Shellphish has evolved to include dozens of
108individuals (graduate students - now professors elsewhere, undergraduate
109students, visitors, their friends, etc.) who are somewhat connected by the
110Security Lab at UC Santa Barbara, but who are now spread all across the
111world. Nonetheless, Shellphish has never lost its "hackademic" background
112and its interest in the science behind hacking. Participation in many CTF
113competitions sparked novel research ideas, which, in addition to
114publications, resulted in tools, which, in turn, were put to good use
115during CTF competitions.
116
117Given the academic focus of Shellphish, it is no surprise that the DARPA
118Cyber Grand Challenge seemed like a great opportunity to put the research
119carried out at the UC Santa Barbara SecLab to work. Unfortunately, when the
120call for participation for the funded track came out, the lab was (as
121usual) busy with a great number of research projects and research
122endeavors, and there were simply no cycles left to dedicate to this effort.
123However, when the call for the qualification round that was open to anybody
124who wanted to throw their hat in the ring was announced, a group of
125dedicated students from the SecLab decided to participate, entering the
126competition as team Shellphish.
127
128With only a few weeks to spare, the Shellphish team put together a
129prototype of a system that automatically identifies crashes in binaries
130using a novel composition of fuzzing and symbolic execution.
131Unsurprisingly, the system was largely unstable and crashed more than the
132binaries it was supposed to crash. Yet, it performed well and Shellphish
133was one of the seven teams (out of more than a hundred participants) that
134qualified for the final event. Since Shellphish was not initially funded by
135DARPA through the funded track, it received a $750,000 award to fund the
136creation of the autonomous system that would participate in the final
137competition.
138
139The following few months focused mostly on basic research, which resulted
140in a number of interesting scientific results in the field of binary
141analysis [Driller16, ArtOfWar16], and to the dramatic improvement of angr
142[angr], an open-source framework created at the UC Santa Barbara SecLab to
143support the analysis of binaries.
144
145Eventually, the pressure to create a fully autonomous system increased to
146the point that academic research had to be traded for system-building.
147During the several months preceding the final competition event, all the
148energy of the Shellphish team focused on creating a solid system that could
149be resilient to failure, perform at scale, and be able not only to crash
150binaries, but also to generate reliable exploits and patches.
151
152After gruesome months of Sushi-fueled work that lead to severe Circadian
153rhythm sleep disorder [Inversion] in many of the team's members, the
154Mechanical Phish Cyber Reasoning System was born. Mechanical Phish is a
155highly-available, distributed system that can identify flaws in DECREE
156binaries, generate exploits (called Proofs Of Vulnerability, or POVs), and
157patched binaries, without human intervention. In a way, Mechanical Phish
158represents a codification of some of the hacking skills of Shellphish.
159
160Mechanical Phish participated in the final event, held in Las Vegas on
161August 4th, in conjunction with DEF CON, and placed third, winning a
162$750,000 prize. As a team, we were ecstatic: our system performed more
163successful exploits than any other CRS, and it was exploited on fewer
164challenges than any other CRS. Of course, in typical Shellphish style, the
165game strategy is where we lost points, but the technical aspects of our CRS
166were some of the best.
167
168We decided to make our system completely open-source (at the time of
169writing, Shellphish is the only team that decided to do so), so that others
170can build upon and improve what we put together.
171
172The rest of this article describes the design of our system, how it
173performed, and the many lessons learned in designing, implementing, and
174deploying Mechanical Phish.
175
176
177
178--[ Contents
179
180 1 - The Cyber Grand Challenge
181
182 2 - Finding Bugs
183
184 3 - Exploiting
185
186 4 - Patching
187
188 5 - Orchestration
189
190 6 - Strategy
191
192 7 - Results
193
194 8 - Warez
195
196 9 - Looking Forward
197
198
199
200--[ 001 - The Cyber Grand Challenge
201
202The Cyber Grand Challenge was run by DARPA, and DARPA is a government
203agency. As such, the amount of rules, regulations, errata, and so forth was
204considerably out of the range with which we were familiar. For example, the
205Frequently Asked Questions document alone, which became the CGC Bible of
206sorts, reached 68 dense pages by the time the final event came around;
207roughly the size of a small novella. This novella held much crucial
208information, and this crucial information had to be absorbed by the team,
209digested, and regurgitated into the squawking maw of the Mechanical Phish.
210
211
212--[ 001.001 - Game Format
213
214The CGC Final Event took the form of a more-or-less traditional
215attack-defense CTF. This means that each team had to attack, and defend
216against, each other team. Counter to A&D CTF tradition, and similar to the
217setup of several editions of the UCSB iCTF, exploits could not be run
218directly against opponents, but had to be submitted to the organizers.
219Likewise, patches could not be directly installed (i.e., with something
220like scp), but had to be submitted through the central API, termed the
221"Team Interface" (TI) by DARPA. This allowed DARPA to maintain full control
222over when and how often attacks were launched, and how patches were
223evaluated.
224
225The CGC was divided into rounds (specifically, there were 95 rounds in the
226final event) of at least 5 minutes each. Each round, the TI specified the
227currently-active challenges. A challenge could be introduced at any point,
228up to a maximum of 30 concurrently active challenges, and was guaranteed to
229remain live for a minimum of 10 rounds.
230
231All teams would start with the same binaries for a challenge. Each round,
232teams could submit patches for their instances of the challenge binaries,
233exploits for the opponents' instances, and network rules to filter traffic.
234Submitted exploits would go "live" on the round *after* the one during
235which they were submitted, while submitted patches and network rules would
236go live 2 rounds after. Submitting a patch, causes that team to incur one
237round of downtime for that challenge, in which opponents can download the
238patched binary. Patched binaries were visible by opponents to allow them
239to exploit incomplete patches.
240
241
242--[ 001.002 - Game Scoring
243
244The CGC employed a scoring algorithm that had serious implications for the
245strategies that were viable for teams to adopt. Each team would be scored
246on a per-round basis, and a team's final score was the sum of all of their
247round scores. A team's round score was, in turn, the sum of their
248"Challenge Binary Round Scores" for that round. This CB Round Score was the
249real crux of the matter.
250
251A CB Round Score was calculated for every Challenge Binary to be a simple
252multiplication of:
253
254- Availability: this was a measure of the performance overhead and
255 functionality impact introduced by a patch. The performance and
256 functionality scores each ranged from 0 (broken) to 100 (perfect), and
257 the availability score was the minimum of these numbers.
258- Security: this number was 2 if the Challenge Binary was secure (i.e.,
259 it had not been exploited by any competitor that round), and 1
260 otherwise (if it was exploited by at least one competitor).
261- Evaluation: this number ranged from 1.0 to 2.0, based on how many
262 opponents the team was hitting with their exploits (if any) for this
263 challenge binary. For example, if an exploit was succeeding against 2 of
264 the 6 opponents, this number would be 1.33.
265
266The round after a patch was submitted or an IDS rule was updated for a
267challenge binary, that challenge binary's availability score would be set
268to 0 and no exploits would be scheduled (either by the patching team or
269against the patching team) for that round.
270
271On the surface, this seems like a simple formula. However, there were
272several complications:
273
274- DARPA did not disclose the formula used to calculate the performance or
275 functionality scores prior to the CFE. While this was presumably done to
276 avoid letting teams "game the system", it led to an astonishing amount of
277 uncertainty regarding patching. Teams knew that they had some "free"
278 overhead (20% for the file size, and 5% each for runtime overhead and
279 memory overhead), but did not know how additional overhead would be
280 penalized.
281- The runtime overhead included overhead introduced by the network IDS as
282 it matched submitted network rules. This overhead was fundamentally
283 unmeasurable before the game. During the CFE, it turned out that the
284 overhead introduced by network rules from one service could actually
285 influence overhead of *other* services. All this uncertainty kept all but
286 two teams from using the network IDS during the CFE.
287- The memory and runtime overhead was astonishingly hard to measure. As we
288 discuss later, local measurements were so unreliable that we actually
289 decided not to test our own patches for performance during the CFE, but
290 optimized the techniques as much as possible beforehand and relied on the
291 TI feedback for already-submitted patches. As we'll also discuss, DARPA
292 themselves had some trouble keeping the measurements constant, with
293 measurements between teams (for identical, unpatched binaries) varying by
294 significant amounts.
295
296Overall, the performance scoring was both a strength and weakness of the
297game. Because of the ease with which exploits can be "broken" by simple
298patches, it was critical to have some patch dis-incentives. However, the
299measurement of such patches is a very hard problem, and led to some chaos.
300
301
302--[ 001.003 - Visibility
303
304With the CGC, DARPA pioneered something called the "Consensus Evaluation".
305This had many implications for many parts of the game, but the biggest one
306was a slight change to the "visibility" of certain aspects of the game to
307the different teams. In this section, we'll detail what information was
308available to competitors during the game.
309
310All interaction with the game was done via the CGC API (what DARPA called
311the Team Interface, or TI). The TI provided the following information:
312
313- The Challenges: all teams could retrieve the challenges that were "in
314 play" at any given moment.
315
316- Patched Binaries: all teams could retrieve the patched binaries of *all*
317 opponents. This prevented opponents from deploying "chump" patches that
318 relied on simple security through obscurity.
319
320- IDS rules: all teams could retrieve the IDS rules that were being fielded
321 by their opponents.
322
323- Availability impacts: a team could see the runtime overhead, memory
324 overhead, and functionality impact of their submitted patches.
325
326- Crashes: a team could see what signals their binaries crashed with as a
327 result of processing network traffic. This could give hints for whether
328 or not exploits were being thrown against a challenge binary.
329
330- Network Traffic: a team could get most of the network traffic, including
331 all exploits and most of the functionality polls (DARPA reserved the
332 right to keep some of them secret).
333
334- POV Feedback: a team could get the results of their own exploits against
335 other teams.
336
337- Round scores: teams could get the overall round scores of all
338 competitors.
339
340This level of visibility is different than your "average" CTF.
341Specifically, the big difference is that the patches submitted by the Cyber
342Reasoning Systems were made available to opponents. In theory, this would
343allow opponents to analyze, and try to bypass, a CRS' patches. In practice,
344as we discussed in the Patching section, patched binaries were too
345"dangerous" to analyze. Teams were allowed to add anti-reversing code, and,
346in our experience, it was easy to find ways to crash analysis tools, or
347"clog" them, causing them to slow down or use extra resources. We did not
348dare to run our heavier analysis on the patched binaries, and we are not
349aware of any team that did. Instead, our heavy analysis was run strictly on
350the original, unpatched binaries, and the patched binaries were run through
351a quick analysis that would fix up memory offsets and so forth in the case
352of "chump" patches.
353
354
355--[ 001.004 - Practice
356
357Full autonomy is difficult to achieve. To mitigate some of this difficulty,
358DARPA provided CGC practice sessions through a "sparring partner". In the
359months leading up to the final event, the sparring partner would connect to
360our Cyber Reasoning System at random, unannounced times and begin a game.
361
362The presence of the sparring partner was immensely helpful in debugging
363interactions with the API. However, the unannounced nature of these events
364meant that it was rarely possible to be ready for this debugging.
365Additionally, since DARPA only had one sparring partner setup, and teams
366had to take turns interacting with it, the sparring partner sessions were
367very short (generally, about 30 minutes, or 5 rounds). The reduced length
368of these sessions made it more difficult to truly stress-test the systems,
369and several teams showed signs of failure due to overload during the final
370event itself.
371
372We mostly used the practice round to test the difference between DARPA's
373calculated overhead from our estimated one. This allowed us to get a vague
374idea of how DARPA calculated overhead, and tailor our patching techniques
375accordingly.
376
377
378--[ 001.005 - DECREE OS
379
380The binaries that made up the Cyber Grand Challenge's challenges were not
381standard Linux binaries. Instead, they were binaries for an OS, called
382DECREE, that was created specifically for the Cyber Grand Challenge. This
383OS was extremely simple: there were 7 system calls, and no persistence
384(i.e., filesystem storage, etc). The DECREE syscalls are:
385
3861. terminate: the equivalent of exit()
3872. transmit: the equivalent of send()
3883. receive: the equivalent of recv()
3894. fdwait: the equivalent of select()
3905. allocate: the equivalent of mmap()
3916. deallocate: the equivalent of munmap()
3927. random: a system call that would generate random data
393
394The hardware platform for the binaries was 32-bit x86. Challenge authors
395were not allowed to include inline assembly code, only code which was
396produced by clang or included in a library provided by DARPA. The provided
397math library included instructions such as floating point logarithms and
398trigonometric operations. All other code had to be produced directly by the
399compiler (clang).
400
401This simple environment model allowed competitors to focus on their program
402analysis techniques, rather than the implementation details that go along
403with support complex OS environments. The DECREE OS was, in the opinion of
404many of us, the biggest thing that made the CGC possible with humanity's
405current level of technology.
406
407
408
409
410--[ 002 - Finding Bugs
411
412
413 -----------------------------------------
414 | Driller |
415 | |
416 | ++++++++++++++ ++++++++++++++ |
417 | + angr + =====> + AFL + |
418 | + + + + |
419 | + Symbolic + + Genetic + |
420 | + Tracing + <===== + Fuzzing + |
421 | ++++++++++++++ ++++++++++++++ |
422 | |
423 -----------------------------------------
424
425
426
427There are a few things we considered when we thought about how we wanted to
428find bugs in the Cyber Grand Challenge. Firstly, we will need to craft
429exploits using the bugs we find. As a result, we need to use techniques
430which generate inputs that trigger the bugs, not just point out that there
431could be a bug. Secondly, the bugs might be guarded by specific checks such
432as matching a command argument, password or checksum. Lastly, the programs
433which we need to analyze might be large, so we need techniques which scale
434well.
435
436The automated bug finding techniques can be divided into three groups:
437static analysis, fuzzing, and symbolic execution. Static analysis is not
438too useful as it doesn't generate inputs which actually trigger the bug.
439Symbolic execution is great for generating inputs which pass difficult
440checks, however, it scales poorly in large programs. Fuzzing can handle
441fairly large programs, but struggles to get past difficult checks. The
442solution we came up with is to combine fuzzing and symbolic execution,
443into a state-of-the-art guided fuzzer, called Driller. Driller uses a
444mutational fuzzer to exercise components within the binary, and then uses
445symbolic execution to find inputs which can reach a different component.
446
447* Fuzzing
448
449Driller leverages a popular off-the-shelf fuzzer, American Fuzzy Lop. AFL
450uses instrumentation to identify the transitions that a particular input
451exercises when it is passed to the program. These transitions are tuples
452of source and destination basic blocks in the control flow graph. New
453transition tuples often represent functionality, or code paths, that has
454not been exercised before; logically, these inputs containing new
455transition tuples are prioritized by the fuzzer.
456
457To facilitate the instrumentation, we use a fork of QEMU, which enables the
458execution of DECREE binaries. Some minor modifications were made to the
459fuzzer and to the emulation of DECREE binaries to enable faster fuzzing as
460well as finding deeper bugs:
461
462- De-randomization
463 Randomization by the program interferes with the fuzzer's evaluation
464 of inputs - an input that hits an interesting transition with one
465 random seed, may not hit it with a different random seed. Removing
466 randomness allows the fuzzer to explore sections of the program which
467 may be guarded by randomness such as "challenge-response" exchanges.
468 During fuzzing, we ensure that the flag page is initialized with a
469 constant seed, and the random system call always returns constant
470 values so there is no randomness in the system. The Exploitation
471 component of our CRS, is responsible for handling the removal of
472 randomness.
473
474- Double Receive Failure
475 The system call receive fails after the input has been completely read
476 in by the program and the file descriptor is now closed. Any binary
477 which does not check the error codes for this failure may enter an
478 infinite loop, which slows down the fuzzer dramatically. To prevent
479 this behavior, if the receive system call fails twice because the
480 end-of-file has been reached, the program is terminated immediately.
481
482- At-Receive Fork Server
483 AFL employs a fork server, which forks the program for each execution
484 of an input to speed up fuzzing by avoiding costly system calls and
485 initialization. Given that the binary has been de-randomized as
486 described above, all executions of it must be identical up until the
487 first call to receive, which is the first point in which non-constant
488 data may enter the system. This allows the fork-server to be moved
489 from the entry of the program, to right before the first call to
490 receive. If there is any costly initialization of globals and data
491 structures, this modification speeds up the fuzzing process greatly.
492
493* Network Seeds
494
495Network traffic can contain valuable seeds which can be given to the
496fuzzer to greatly increase the fuzzing effectiveness. Functionality tests
497exercise deep functionality within the program and network traffic from
498exploits may exercise the particular functionality which is buggy. To
499generate seeds from the traffic, each input to the program is run with the
500instrumentation from QEMU to identify if it hits any transitions which
501have not been found before. If this condition is met, the input is
502considered interesting and is added as a seed for the fuzzer.
503
504* Adding Symbolic Execution
505
506Although symbolic execution is slow and costly, it is extremely powerful.
507Symbolic execution uses a constraint solver to generate specific inputs
508which will exercise a given path in the binary. As such, it can produce
509the inputs which pass a difficult check such as a password, a magic
510number, or even a checksum. However, an approach based entirely on
511symbolic execution will quickly succumb to path explosion, as the number
512of paths through the binary exponentially increases with each branch.
513
514Driller mitigates the path-explosion problem by only tracing the paths
515which the fuzzer, AFL, finds interesting. This set of paths is often small
516enough that tracing the inputs in it is feasible within the time
517constraints of the competition. During each symbolic trace, Driller
518attempts to identify transitions that have not yet been exercised by the
519fuzzer, and, if possible, it generates an input which will deviate from
520the trace and take a new transition instead. These new inputs are fed back
521into the fuzzer, where they will be further mutated to continue exercising
522deeper paths, following the new transitions.
523
524* Symbolic Tracing
525
526To ensure that the symbolic trace using angr's concolic execution engine
527is identical to the native execution trace, we use pre-constraining. In
528pre-constrained execution, each byte of input is constrained to match the
529original byte of input that was used by the fuzzer. When a branch is
530reached that would lead to a new transition, the pre-constraints are
531removed and then the solver is queried for an input which reaches the new
532transition. Pre-constraining also has the benefit of greatly improving
533execution time, because one does not need to perform expensive solves to
534determine the locations of reads and writes to memory because all
535variables have only one possible value.
536
537
538
539
540
541--[ 003 - The Exploiting Component
542
543
544 Crashes Inputs
545 || ||
546 || ||
547 ======================== ||
548 || || ||
549 || || ||
550 \/ \/ \/
551 -------------------- -------------------- --------------------
552 | REX | | PovFuzzer | | Colorguard |
553 | | | | | |
554 | ++++++++++++++ | | ++++++++++++++ | | ++++++++++++++ |
555 | + Advanced + | | + Fuzzing + | | + Finding + |
556 | + AEG + | | + For + | | + Leaks + |
557 | + + | | + Exploits + | | + + |
558 | ++++++++++++++ | | ++++++++++++++ | | ++++++++++++++ |
559 | | | | | |
560 | ... | | | | |
561 -------------------- -------------------- --------------------
562 || || ||
563 ================================================
564 ||
565 \/
566 POVs
567
568
569* Exploitation
570
571In the Cyber Grand Challenge, stealing flags is a little different than
572it is in ordinary Capture the Flag games. Instead of reading a secret
573"flag" file and submitting the contents to the organizers, an exploit is
574demonstrated by submitting a Proof of Vulnerability (POV), which the
575organizers will run.
576
577A POV is a binary program, which will communicate with the opponent's
578binary and "exploit" it. There are two ways in which a POV can be
579considered successful:
580- Type 1: Cause a segmentation fault where the instruction pointer and one
581 additional register have values which were previously negotiated
582 with the competition infrastructure. Must control at least
583 20 bits of EIP as well as 20 bits of another register.
584- Type 2: Read 4 contiguous bytes from the secret flag data. The flag data
585 is located at 0x4347c000-0x4347cfff and is randomly initialized
586 by the kernel.
587
588Different types of vulnerabilities might lend themselves to a specific
589type of POV. For example, a vulnerability where the user can control the
590address passed to puts() might only be usable as a Type 2 POV. On the
591other hand, a stack-based buffer overflow can clearly be used to create a
592Type 1 exploit simply by setting a register and EIP, but it can also be
593used to create a Type 2 exploit by using Return Oriented Programming or by
594jumping to shellcode which prints data from the flag page.
595
596* Overview
597
598The basic design for Mechanical Phish's automatic exploitation is to take
599crashes, triage them, and modify them to create exploits. Mechanical Phish
600does not need to understand the root cause of the bug, instead it only
601needs to identify what registers and memory it controls at crash time, and
602how those values can be set to produce a POV. We created two systems which
603are designed to go from crashes to exploits.
604
605- PovFuzzer
606 Executes the binary repeatedly, slightly modifying the input,
607 tracking the relationship between input bytes and registers at the
608 crash point. This method is fast, but cannot handle complex cases.
609
610- Rex
611 Symbolically executes the input, tracking formulas for all registers
612 and memory values. Applies "techniques" on this state, such as
613 jumping to shellcode, and return oriented programming to create a POV.
614
615Now this design was missing one important thing. For some challenges the
616buggy functionality does not result in a crash! Consider a buffer
617over-read, where it reads passed the end of the buffer. This may not cause
618a crash, but if any copy of flag data is there, then it will print the
619secret data. To handle this, we added a third component.
620
621- Colorguard
622 Traces the execution of a binary with a particular input and
623 checks for flag data being leaked out. If flag data is leaked, then
624 it uses the symbolic formulas to determine if it can produce a valid
625 POV.
626
627
628--[ 003.001 - PovFuzzer
629
630The PovFuzzer takes a crash and repeatedly changes a single byte at a time
631until it can determine which bytes control the EIP as well as another
632register. Then a Type 1 POV can be constructed which simply chooses the
633input bytes that correspond to the negotiated EIP and register values,
634inserts the bytes in the payload, and sends it to the target program.
635
636For crashes which occur on a dereference of controlled data, the PovFuzzer
637chooses bytes that cause the dereference to point to the flag page, in the
638hope that flag data will be printed out. After pointing the dereference at
639the flag page, it executes the program to check if flag data is printed
640out. If so, it constructs a Type 2 POV using that input.
641
642The PovFuzzer has many limitations. It cannot handle cases where register
643values are computed in a non-trivial manner, such as through
644multiplication. Furthermore it cannot handle construction of more complex
645exploits such as jumping to shellcode, or where it needs to replay a random
646value printed by the target program. Even so, it is useful for a couple
647reasons. Firstly, it is much faster than Rex, because it only needs to
648execute the program concretely. Secondly, although we don't like to admit
649it, angr might still have occasional bugs, and the PovFuzzer is a good
650fallback in those cases as it doesn't rely on angr.
651
652
653--[ 003.002 - Rex
654
655The general design of Rex is to take a crashing payload, use angr to
656symbolically trace the program with the crashing payload, collecting
657symbolic formulas for all memory and input along the way. Once we hit the
658point where the program crashes, we stop tracing, but use the constraint
659solver to pick values that either make the crash a valid POV, or avoid the
660crash to explore further. There are many ways we can choose to constrain
661the values at this point, each of which tries to exploit the program in a
662different way. These methods of exploiting the program are called
663"techniques".
664
665One quick thing to note here is that we include a constraint solver in our
666POVs. By including a constraint solver we can simply add all of the
667constraints collected during tracing and exploitation into the POV and
668then ask the constraint solver at runtime for a solution that matches the
669negotiated values. The constraint solver, as well as angr, operates on
670bit-vectors enabling the techniques to be bit-precise.
671
672Here we will describe the various "techniques" which Rex employs.
673
674- Circumstantial Exploit
675 This technique is applicable for ip-overwrite crashes and is the
676 simplest technique. It determines if at least 20 bits of the
677 instruction pointer and one register are controlled by user input. If
678 so, an exploit is constructed that will negotiate the register and ip
679 values and then solve the constraints to determine the user input
680 that sets them correctly.
681
682- Shellcode Exploit
683 Also only applicable to ip-overwrites, this technique will search for
684 regions of executable memory that are controlled by user input. The
685 largest region of controlled executable memory is chosen and the
686 memory there is constrained to be a nop-sled followed by shellcode to
687 either prove a type-1 or type-2 vulnerability. A shellcode exploit
688 can function even if the user input only controls the ip value, and
689 not an additional register.
690
691- ROP Exploit
692 Although the stack is executable by default, opponents might employ
693 additional protections that prevent jumping to shellcode, such as
694 remapping the stack, primitive Address Randomization or even some
695 form of Control Flow Integrity. Return Oriented Programming (ROP) can
696 bypass incomplete defenses and still prove vulnerabilities for
697 opponents that employ them. It is applicable for ip-overwrite crashes
698 as long as there is user data near the stack pointer, or the binary
699 contains a gadget to pivot the stack pointer to the user data.
700
701- Arbitrary Read - Point to Flag
702 A crash that occurs when the program tries to dereference user-
703 controlled data is considered an "arbitrary read". In some cases, by
704 simply constraining the address that will be dereferenced to point at
705 flag data, the flag data will be leaked to stdout, enabling the
706 creation of a type-2 exploit. Point to Flag constrains the input to
707 point at the flag page, or at any copy of flag data in memory, then
708 uses Colorguard to determine if the new input causes an exploitable
709 leak.
710
711- Arbitrary Read/Write - Exploration
712 In some cases, the dereference of user-controlled data can lead to a
713 more powerful exploit later. For example, a vtable overwrite will
714 first appear as an arbitrary read, but if that memory address points
715 to user data, then the read will result in a controlled ip. To
716 explore arbitrary reads/writes for a better crash, the address of the
717 read or write is constrained to point to user data, then the input is
718 re-traced as a new crash.
719
720- Write-What-Where
721 If the input from the user controls both the data being written and
722 the address to which it is written, we want to identify valuable
723 targets to overwrite. This is done by symbolically exploring the
724 crash, to identify values in memory that influence the instruction
725 pointer, such as return addresses or function pointers. Other
726 valuable targets are pointers that are used to print data;
727 overwriting these can lead to type-2 exploits.
728
729
730--[ 003.003 - Colorguard
731
732As explained above, there are some challenges which include
733vulnerabilities that can leak flag data, but do not cause a crash. One
734challenge here is that it is difficult to detect when a leak occurs. You
735can check if any 4 bytes of output data are contained in the flag page,
736but this will have false positives while fuzzing, and it will miss any
737case where the data is not leaked directly. The challenge authors seem to
738prefer to xor the data or otherwise obfuscate the leak, maybe to prevent
739such a method.
740
741To accurately detect these leaks we chose to trace the inputs
742symbolically, using angr. However, symbolic tracing is far too slow to run
743on every input that the fuzzer generates. Instead, we only perform the
744symbolic tracing on the inputs which the fuzzer considers "interesting".
745The hope here is that the leak causing inputs have a new transition, or
746number of loops which is unique, and that the fuzzer will consider it
747interesting. There are definitely cases where this doesn't work, but it's
748a fairly good heuristic for reducing the number of traces.
749
750In an effort to further combat the slowness of symbolic execution,
751Colorguard takes advantage of angr's concrete emulation mode. Since no
752modification of the input has to be made if a flag leak is discovered, our
753input is made entirely concrete, with the only symbolic data being that
754from the flag page. This allows us to only execute symbolically
755those basic blocks that touch the secret flag page contents.
756
757Colorguard traces the entire input concretely and collects the symbolic
758expression for the data that is printed to stdout. The expression is
759parsed to identify any four consecutive bytes of the flag page that are
760contained in the output. For each set of bytes, the solver is queried to
761check if we can compute the values of the bytes only from the output data.
762If so, then an exploit is crafted which solves for these four bytes after
763receiving the output from the program execution.
764
765One caveat here is that challenges may use many bytes of the flag page as
766a random seed. In these cases we might see every byte of the flag page as
767part of the expression for stdout. Querying the constraint solver for
768every one of these consecutive four byte sequences is prohibitively slow,
769so it is necessary to pre-filter such expressions. Colorguard does this
770pre-filter during the trace by replacing any expression containing more
771than 13 flag bytes with a new symbolic variable. The new symbolic variable
772is not considered a potential leak. The number 13 was arbitrarily chosen
773as it was high enough to still detect all of the leaks we had examples for,
774but low enough that checking for leaks was still fast.
775
776
777--[ 003.004 - Challenge Response
778
779A common pattern that still needs to be considered is where the binary
780randomly chooses a value, outputs it, and then requires the user to input
781that value or something computed from the random value. For example, the
782binary prints "Solve the equation: 6329*4291" and then the user must input
783"27157739". To handle these patterns in the exploit, we identify any
784constraints that involve both user input and random data. Once identified,
785we check the output that has been printed up to that point if it contains
786the random data. If so, then we have identified a challenge-response. We
787will include the output as a variable in the constraints that are passed
788to the exploit, and then read from stdout, adding constraints that the
789output bytes match what is received during the exploit. Then the solver
790can be queried to generate the input necessary for the correct "response".
791
792
793
794--[ 004 - The Patching Component: Patcherex
795
796 Original
797 Binary (CB)
798 ||
799 ||
800 ||===============================================
801 || ||
802 || ||
803 \/ \/
804 -------------------- -------------------- --------------------
805 | TECHNIQUES | | PATCHES | | BACKENDS |
806 | | | | | |
807 | ++++++++++++++ | | | | |
808 | + Return + | | - AddROData() | | |
809 | + Pointer + --------> - AddCode() | | +++++++++++++++ |
810 | + Encryption + | | - ... | | + Detour + |
811 | ++++++++++++++ | | | | + Backend + |
812 | | | | | + + |
813 | ++++++++++++++ | | | | +++++++++++++++ |
814 | + Transmit + | | - InsertCode() | | |
815 | + Protection + --------> - AddRWData() |==>| OR |
816 | + + | | - ... | | |
817 | ++++++++++++++ | | | | +++++++++++++++ |
818 | | | | | + Reassembler + |
819 | ++++++++++++++ | | | | + Backend + |
820 | + + | | - AddCode() | | + + |
821 | + Backdoor + --------> - AddRWData() | | +++++++++++++++ |
822 | + + | | - ... | | |
823 | ++++++++++++++ | | | | |
824 | | | | | |
825 | ... | | | | |
826 -------------------- -------------------- --------------------
827 ||
828 ||
829 \/
830 Replacement
831 Binary (RB)
832
833
834Patcherex, which is built on top of angr, is the central patching system of
835Mechanical Phish. As illustrated in the overview image, Patcherex is
836composed of three major components: techniques, patches, and patching
837backends.
838
839* Techniques
840
841A technique is the implementation of a high-level patching strategy. A set
842of patches (described below) with respect to a binary are generated after
843applying a technique on it. Currently Patcherex implements three different
844types of techniques:
845
846- Generic binary hardening techniques, including Return Pointer Encryption,
847 Transmit Protection, Simple Control-Flow Integrity, Indirect Control-Flow
848 Integrity, Generic Pointer Encryption;
849- Techniques aiming at preventing rivals from analyzing or stealing our
850 patches, including backdoors, anti-analysis techniques, etc.;
851- Optimization techniques that make binaries more performant, including
852 constant propagation, dead assignment elimination, and redundant stack
853 variables removal.
854
855* Patches
856
857A Patch is a low-level description of how a fix or an improvement should be
858made on the target binary. Patcherex defines a variety types of patches to
859perform tasks ranging from code/data insertion/removal to segment altering.
860
861* Backends
862
863A backend takes patches generated from one or more techniques, and applies
864them on the target binary. Two backends available in Patcherex:
865
866- ReassemblerBackend: this backend takes a binary, completely disassembles
867 the entire binary, symbolizes all code and data references among code and
868 data regions, and then generate an assembly file. It then apply patches
869 on the assembly file, and calls an external assembler (it was clang for
870 CGC) to reassemble the patched assembly file to the final binary.
871- DetourBackend: this backend acts as a fallback to the
872 ReassemblerBackend. It performs in-line hooking and detouring to apply
873 patches.
874
875
876--[ 004.001 - Patching Techniques
877
878In this section, we describe all techniques we implemented in Patcherex.
879
880Obviously we tried to implement techniques that will prevent exploitation
881of the given CBs, by making their bugs not exploitable. In some cases,
882however, our techniques do not render the bugs completely unexploitable,
883but they still force an attacker to adapt its exploits to our RBs. For
884instance, some techniques introduce differences in the memory layout
885between our generated RB and the original CB an attacker may have used to
886develop its exploit. In addition, we try to prevent attackers from adapting
887exploits to our RB by adding anti-analysis techniques inside our generated
888binaries. Furthermore, although we put a significant effort in minimizing
889the speed and memory impact of our patches, it is often impossible to have
890performance impact lower than 5% (a CB score starts to be lowered when it
891has more than 5% of speed or memory overhead). For this reason we decided
892to "optimize" the produced RB, as we will explain later.
893
894--[ 004.001.001 - Binary Hardening Techniques
895
896We implemented some techniques for generic binary hardening. Those general
897hardening techniques, although not extremely complex, turned out to be very
898useful in the CFE.
899
900Vulnerability-targeted hardening (targeted patching) was also planned
901initially. However, due to lack of manpower and fear for deploying
902replacement CBs too many times for the same challenge, we did not fully
903implement or test our targeted patching strategies.
904
905* Return Pointer Encryption
906
907This technique was designed to protect from classical stack buffer
908overflows, which typically give an attacker control over an overwritten
909saved return pointer. Our defense mechanism "encrypts" every return pointer
910saved on the stack when a function is called, by modifying the function's
911prologue. The encrypted pointer is then "decrypted" before every ret
912instruction terminating the same function. For encryption and decryption we
913simply xor'ed the saved return pointer with a nonce (randomly generated
914during program's startup). Since the added code is executed every time a
915function is called, we take special care in minimizing the performance
916impact of this technique.
917
918First of all, this technique is not applied in functions determined as
919safe. We classify a function as safe if one of these three conditions is
920true:
921
922- The function does not access any stack buffer.
923- The function is called by more than 5 different functions. In this case,
924 we assume that the function is some standard "utility" function, and it
925 is unlikely that it contains bugs. Even if it contains bugs, the
926 performance cost of patching such a function is usually too high.
927- The function is called by printf or free. Again, we assume that library
928 functions are unlikely to contain bugs. These common library functions
929 are identified by running the functions with test input and output pairs.
930 This function identification functionality is offered by a separate
931 component (the "Function identifier" mentioned in the "Warez" Section).
932
933To further improve the performance, the code snippet that encrypts and
934decrypts the saved return pointer uses, when possible, a "free" register to
935perform its computations. This avoids saving and restoring the value of a
936register every time the injected code is executed. We identify free
937registers (at a specific code location) by looking for registers in which a
938write operation always happens before any read operation. This analysis is
939performed by exploring the binary's CFG in a depth-first manner, starting
940from the analyzed code location (i.e., the location where the code
941encrypting/decrypting the return pointer is injected).
942
943Finally, to avoid negatively impacting the functionality of the binary, we
944did not patch functions in which the CFG reconstruction algorithm has
945problems in identifying the prologue and the epilogues. In fact, in those
946cases, it could happen that if an epilogue of the analyzed function is not
947identified, the encrypted return address will not be decrypted when that
948epilogue is reached, and consequently the program will use the
949still-encrypted return pointer on the stack as the return target. This
950scenario typically happens when the compiler applies tail-call
951optimizations by inserting jmp instructions at the end of a function.
952
953* Transmit Protection
954
955As a defense mechanism against Type 2 exploits, we inject code around the
956transmit syscall so that a binary is forbidden from transmitting any 4
957contiguous bytes of the flag page. The injected code uses an array to
958keep track of the last transmitted bytes so that it can identify cases
959in which bytes of the flag page are leaked one at a time.
960
961* Simple Control-Flow Integrity
962
963To protect indirect control flow instructions (e.g., call eax, jmp ebx), we
964inject, before any instruction of this kind, code that checks specific
965properties of the target address (i.e., the address which the instruction
966pointer will be after the call or jump). The specific checks are:
967
968- The target address must be an allocated address (to prevent an attacker
969from using the indirect control-flow instruction to directly perform a
970Type 1 attack). To do so, we try to read from the target address, so that
971if the address does not point to an allocated region the program will crash
972before the instruction pointer is modified. This prevents simple Type 1
973exploits, because the attacker must control at least 20 bits of the
974instruction pointer, and it is unlikely (but not impossible) that the
975negotiated value will end up inside an allocated memory region.
976
977- The target address must be inside the memory range where the binary's
978code is typically loaded (for simplicity, we consider a "potential code"
979address to be any below 0x4347c000). To avoid breaking programs that use
980dynamically allocated code we do not perform this check if we statically
981detect that the analyzed program calls the allocate syscall in a way which
982will create additional executable memory.
983
984- The target address is not a pop instruction. As a partial mitigation
985against ROP attacks, we dynamically check if the target of indirect calls
986is a pop instruction, and terminate the program otherwise.
987
988* Uninitialized Data Cleaning
989
990For each function, we identify all of the instructions that read and write
991to stack variables, and the stack offset that is accessed. If there is any
992path through the CFG such that a stack variable is read before it is
993written, then we consider it possible that there is an uninitialized data
994usage. For each variable that is detected in an uninitialized data usage,
995we zero that variable by adding stack cleaning code at the beginning of the
996function.
997
998* Stack Base Address Randomization
999
1000On program's startup we add a random value (which can assume any 16-byte
1001aligned value between 16 and 1024) to the stack pointer address. This adds
1002indeterminism to the position of the stack, hindering any exploit making
1003assumptions on the program's stack layout.
1004
1005* malloc Protection
1006
1007To interfere with exploitation of heap overflows, if we are able to
1008identify a malloc-like function inside the analyzed CB, we slightly modify
1009its behavior. In particular, we change the amount of bytes allocated by a
1010small, pseudo-random, value.
1011
1012* printf Protection
1013
1014For every printf-like function identified, such as printf, snprintf, etc.,
1015we ensure that the function is not used to perform a "format string"
1016attack. Specifically, if the format string parameter is neither in the
1017binary's read-only memory nor a string already present in the binary, we
1018stop the execution of the binary if:
1019- The format string parameter contains a meta character (e.g., "%").
1020- The format string parameter points to the flag page.
1021
1022
1023--[ 004.001.002 - Adversarial Techniques
1024
1025Certain techniques are introduced to prevent rivals from analyzing, or even
1026running our RBs in a controlled environment, while leaving those RBs still
1027able to run in the real game environment. These techniques are presented in
1028this section.
1029
1030* Anti-analysis
1031
1032We add some code, executed before the original entry point of the binary,
1033to interfere with analyses that other teams could perform on our patched
1034binary. Specifically, we add code to:
1035- Detect if the binary is executed using QEMU or PIN. To do so, we probe
1036 the implementation of different aspects that are difficult to emulate
1037 correctly, such as segment registers, transmission of partially allocated
1038 memory regions, syscall error codes values in case of "double failure".
1039 In addition, we add some code triggering a previously unknown
1040 implementation bug in QEMU, making it stall. Specifically, during the
1041 development of our CRS, we found that QEMU, when using user-mode
1042 emulation, does not correctly handle taking the square root of an
1043 "un-normal" floating point number, that is, a nonzero 80-bit float whose
1044 explicit integer bit (the highest bit of the mantissa) is zero. When this
1045 happens, QEMU will hang forever. Because of this anti-QEMU patch, some of
1046 our RBs broke the live visualization during the CFE public event.
1047- Interfere with symbolic execution engines. Our adversarial code contains
1048 self-modifying code designed to be extremely hard to simulate correctly
1049 and efficiently by a symbolic execution engine. In addition, some added
1050 code is specifically designed to trigger "path explosion" conditions.
1051- Interfere with automatic exploitation systems. We add code to transmit
1052 the flag page to file descriptor 2 (stderr). Although data transmitted to
1053 this file descriptor is not sent to a CRS interacting with a binary, an
1054 opponent could mistakenly assume that any contiguous 4 bytes transmitted
1055 from the flag page constitutes a Type 2 exploit and thus fielding a POV
1056 trying to leverage this "fake" leak. In addition, we inject "fake
1057 backdoor" code. This code is triggered if a CRS sends a specific 4-byte
1058 sequence. When triggered, it reads from the CRS 8 bytes used to set the
1059 program instruction pointer and the value of a register. For this reason,
1060 this code looks like easily exploitable to create a Type 1 POV, however
1061 the read values are xor'ed with a random value, before being used to set
1062 the instruction pointer and the register, making this code
1063 non-exploitable.
1064
1065In addition, to counteract an adversary fielding one of our own patched
1066binaries as its own patched binary, we inject a backdoor in every fielded
1067patched binary. This backdoor can be used by our CRS to exploit the patched
1068binary we generate, but it is designed to be extremely hard to be exploited
1069from other teams' CRSs. The backdoor is triggered when a specific 4-byte
1070sequence is received. To detect this, the function wrapping the receive
1071syscall is modified to keep track of the first 4 bytes a program receives.
1072Once triggered, the backdoor sends to the CRS a "challenge" C (which is a
107319-bit value), and the CRS responds with a response R (a 64-bit value).
1074Then, the backdoor code checks if the following condition is true:
1075first_32_bits_of(SHA1(pad(R,160))) == pad(C,32), where pad(A,N) is a
1076function padding the input value A up to N bits by adding zeros.
1077
1078The challenge can be easily solved by pre-computing all the possible
1079responses, but it is impossible for an opponent's POV to compute a solution
1080for the challenge within the game-imposed 10-second timeout.
1081
1082
1083--[ 004.001.003 - Optimization Techniques
1084
1085Performance is a vital concern of our patching strategy. While we stress
1086the necessity of optimizing all our patching techniques, some overhead
1087cannot be avoided. From analyzing binaries collected from CQE and CFE
1088samples, we noticed that most of them are compiled with O0, i.e., without
1089optimization enabled. We do not know why organizers decided not to optimize
1090most of the provided challenges, but we speculated that this may have been
1091decided to leave room for optimizations and patching.
1092
1093It is well-known that O0 and O1 binaries can have a huge difference in
1094execution time. Fortunately, some of the optimization methods used in O1
1095are not that difficult to perform directly on binaries. Further, angr
1096provides all necessary data-flow analysis techniques, which makes the whole
1097optimization development easier. Finally, with the help of the
1098ReassemblerBackend, we can easily fully remove instructions that we want to
1099get rid of, without having to replace them with nops. Therefore, we
1100implemented some basic in-line binary optimization techniques in order to
1101optimize O0 binaries in CFE, which are described below.
1102
1103
1104- Constant Propagation. We propagate constants used as immediates in each
1105 instruction, and eliminate unnecessary mov instructions in assembly code.
1106- Dead Assignment Elimination. Many unnecessary assignments occur in
1107 unoptimized code. For example, in unoptimized code, when a function reads
1108 arguments passed from the stack, it will always make a copy of the
1109 argument into the local stack frame, without checking if the argument is
1110 modified or not in the local function. We perform a conservative check
1111 for cases where a parameter is not modified at all in a function and the
1112 copy-to-local-frame is unnecessary. In this case, the copy-to-local
1113 instruction is eliminated, and all references to the corresponding
1114 variable on the local stack frame are altered to reference the original
1115 parameter on the previous stack frame. Theoretically, we may break the
1116 locality, but we noticed some improvement in performance in our off-line
1117 tests.
1118- Redundant Stack Variable Removal. In unoptimized code, registers are not
1119 allocated optimally, and usually many registers end up not being used. We
1120 perform a data-flow analysis on individual functions, and try to replace
1121 stack variables with registers. This technique works well with variables
1122 accessed within tight loops. Empirically speaking, this technique
1123 contributes the most to the overall performance gain we have seen during
1124 testing.
1125
1126Thanks to these optimizations, our patches often had *zero* overall
1127performance overhead.
1128
1129--[ 004.002 - Patches
1130
1131The techniques presented in the previous section return, as an output,
1132lists of patches. In Patcherex, a patch is a single modification to a
1133binary.
1134
1135The most important types of patches are:
1136
1137- InsertCodePatch: add some code that is going to be executed before an
1138 instruction at a specific address.
1139- AddEntryPointPatch: add some code that is going to be executed before the
1140 original entry point of the binary.
1141- AddCodePatch: add some code that other patches can use.
1142- AddRWData: add some readable and writable data that other patches can
1143 use.
1144- AddROData: add some read-only data that other patches can use.
1145
1146Patches can refer to each other using an easy symbol system. For instance,
1147code injected by an InsertCodePatch can contain an instruction like call
1148check_function. In this example, this call instruction will call the code
1149contained in an InsertCodePatch named check_function.
1150
1151
1152--[ 004.003 - Backends
1153
1154We implemented two different backends to inject different patches. The
1155DetourBackend adds patches by inserting jumps inside the original code,
1156whereas the ReassemblerBacked adds code by disassembling and then
1157reassembling the original binary. The DetourBackend generates bigger (thus
1158using more memory) and slower binaries (and in some rare cases it cannot
1159insert some patches), however it is slightly more reliable than the
1160ReassemblerBackend (i.e., it breaks functionality in slightly less
1161binaries).
1162
1163* DetourBackend
1164
1165This backend adds patches by inserting jumps inside the original code. To
1166avoid breaking the original binary, information from the CFG of the binary
1167is used to avoid placing the added jmp instruction in-between two basic
1168blocks. The added jmp instruction points to an added code segment in which
1169first the code overwritten by the added jmp and then the injected code is
1170executed. At the end of the injected code, an additional jmp instruction
1171brings the instruction pointer back to its normal flow.
1172
1173In some cases, when the basic block that needs to be modified is too small,
1174this backend may fail applying an InsertCodePatch. This requires special
1175handling, since patches are not, in the general case, independent (a patch
1176may require the presence of another patch not to break the functionality of
1177a binary). For this reason, when this backend fails in inserting a patch,
1178the patches "depending" from the failed one are not applied to the binary.
1179
1180* ReassemblerBackend
1181
1182ReassemblerBackend fully disassembles the target binary, applies all
1183patches on the generated assembly, and then assembles the assembly back
1184into a new binary. This is the primary patching backend we used in the CFE.
1185Being able to fully reassemble binaries greatly reduces the performance hit
1186introduced by our patches, and enables binary optimization, which improves
1187the performance of our RBs even further. Also, reassembling usually changes
1188base addresses and function offsets, which achieves a certain level of
1189"security by obscurity" -- rivals will have to analyze our RBs if they want
1190to properly adapt their code-reusing and data-reusing attacks.
1191
1192We provide an empirical solution for binary reassembling that works on
1193almost every binary from CQE and CFE samples. The technique is open-sourced
1194as a component in angr, and, after the CGC competition, it has been
1195extended to work with generic x86 and x86-64 Linux binaries.
1196
1197A detailed explanation as well as evaluation of this technique is published
1198as an academic paper [Ramblr17].
1199
1200--[ 004.004 - Patching Strategy
1201
1202We used Patcherex to generate, for every CB, three different Replacement
1203Binaries (RBs):
1204
1205- Detouring RB: this RB was generated by applying, using the DetourBackend,
1206 all the patches generated by the hardening and adversarial techniques
1207 presented previously.
1208- Reassembled RB: this RB was generated by applying the same patches used
1209 by the Detouring RB, but using the ReassemblerBackend instead of the
1210 DetourBackend.
1211- Optimized Reassembled RB: this RB was generated as the Reassembled one,
1212 but, in addition all the patches generated by the optimization techniques
1213 were added.
1214
1215These three patched RBs have been listed in order of decreasing performance
1216overhead and decreasing reliability. In other words, the Detouring RB is
1217the most reliable (i.e., it has the smallest probability of having broken
1218functionality), but it has the highest performance overhead with respect to
1219the original unpatched binary. On the contrary the Optimized Reassembled RB
1220is the most likely to have broken functionality, but it has a lower
1221performance impact.
1222
1223
1224--[ 004.005 - Replacement Binary Evaluation
1225
1226* Pre-CFE Evaluation
1227
1228During initial stages of Patcherex development, testing of the RBs was done
1229by an in-house developed component called Tester. Internally, Tester uses
1230cb-test, a utility provided by DARPA for testing a binary with
1231pre-generated input and output pairs, called polls. We made modifications
1232to cb-test, which enabled the testing of a binary and its associated IDS
1233rules on a single machine, whereas the default cb-test needs 3-machines to
1234test a binary with IDS rules.
1235
1236Tester can perform both performance and functionality testing of the
1237provided binary using the pre-generated polls for the corresponding binary
1238using its Makefile. For functionality testing, given a binary, we randomly
1239pick 10 polls and check that the binary passes all the polls. For
1240performance testing, we compute the relative overhead of the provided
1241binary against the unpatched one using all the polls. However, there was
1242huge discrepancy (~10%) between the performance overhead computed by us and
1243that provided during sparring partner sessions for the same binaries.
1244Moreover, during the sparring partner sessions, we also noticed that
1245performance numbers were different across different rounds for the same
1246binaries. Because of these discrepancies and to be conservative, for every
1247patching strategy, we computed the performance overhead as the maximum
1248overhead across all rounds of sparring partner sessions during which RBs
1249with corresponding patching strategy are fielded.
1250
1251During internal testing we used all the available binaries publicly
1252released on GitHub (some of which were designed for the CQE event, whereas
1253others were sample CFE challenges). To further extend our test cases, we
1254recompiled all the binaries using different compilation flags influencing
1255the optimization level used by the compiler. In fact, we noticed that
1256heavily optimized binaries (e.g., -O3), were significantly harder to
1257analyze and to patch without breaking functionality. Specifically, we used
1258the following compilations flags: -O0, -Os, -Oz, -O1, -O2, -O3, -Ofast.
1259Interestingly, we noticed that some of the binaries, when recompiled with
1260specific compilation flags, failed to work even when not patched.
1261
1262During the final stages of Patcherex development, we noticed that almost
1263all generated RBs never failed the functionality and that the performance
1264overhead was reasonable except for a few binaries. This, combined with the
1265discrepancy inherent in performance testing, led us not to use any in-depth
1266testing of our replacement binaries during the CFE.
1267
1268* CFE Evaluation
1269
1270For every RB successfully generated, Patcherex first performs a quick test
1271of their functionality. The test is designed to spot RBs that are broken by
1272the patching strategy. In particular, Patcherex only checks that every
1273generated RB does not crash when provided with a small test set of
1274hardcoded input strings ("B", "\n", "\n\n\n\n\n\n", etc.)
1275
1276We decided to perform only a minimal tests of the functionality because of
1277for performance and reliability considerations.
1278
1279--[ 004.006 - Qualification Round Approaches
1280
1281It is worth mentioning that for the CGC qualification round, the rules were
1282very different from the final round. Between this and the fact that our
1283analysis tools were not yet mature it was necessary for us to approach
1284patching very differently from the final round approaches previously
1285described.
1286
1287In the qualification round, the only criteria for "exploitation" was a
1288crash. If you could crash a binary, it meant that you could exploit it, and
1289if your binary could crash, it meant that you were vulnerable. Furthermore,
1290the qualification scoring formula was such that your "defense" score, i.e.
1291how many vulnerabilities your patch protected against, was a global
1292multiplier for your score between zero and one. This meant that if you
1293didn't submit a patch for a binary, or if your patch failed to protect
1294against any of the vulnerabilities, you received zero points for that
1295challenge, regardless of how well you were able to exploit it.
1296
1297This is such an unconventional scoring system that when we analyzed the
1298(publicly available) patches produced by other teams for the qualification
1299round, we found that at least one qualifying team had a patching strategy
1300such that whenever they discovered a crash, they patched the crashing
1301instruction to simply call the exit syscall. This is technically not a
1302crash, so the teams that did this did in fact receive defense points for
1303the challenges, and accordingly did in fact receive a non-negligible score
1304for effectively stubbing out any vaguely problematic part of the binary.
1305
1306Our approaches were slightly more nuanced! There were two techniques we
1307developed for the qualification round, one "general" technique, meaning
1308that it could be applied to a program without any knowledge of the
1309vulnerabilities in a binary, and one "targeted" technique, meaning that it
1310was applied based on our CRS' knowledge of a vulnerability. Each of the
1311techniques could produce several candidate patched binaries, so we had to
1312choose which one to submit in the end - our choice was based on some
1313rudimentary testing to try to ascertain if the binary could still crash,
1314and if not, to assess the performance impact of the patch.
1315
1316It is important to notice for CQE, the patched binaries were tested by the
1317organizers against a fixed set of pre-generated exploits. For this reason,
1318our patched binaries just had to prevent to be exploited when run against
1319exploit developed for the original, unpatched, version of the program. In
1320other words, the attacker had no way to adapt its exploits to our patches
1321and so "security trough obscurity" techniques were extremely effective
1322during the qualification event.
1323
1324
1325--[ 004.006.001 - Fidget
1326
1327Our "general" patching technique for CQE was a tool called Fidget. Fidget
1328was developed the summer prior to the announcement of the CGC for use in
1329attack-defense CTFs. Its basic intuition is that the development of an
1330attack makes a large number of very strong assumptions about the internal
1331memory layout of a program, so in many cases simply tweaking the layout of
1332stack variables is a reliable security-through-obscurity technique.
1333
1334At the time of the CQE, Fidget was a tool capable of expanding function
1335stack frames, putting unused space in between local variables stored on the
1336stack. This is clearly not sufficient to prevent crashes, as is necessary
1337for the strange qualification scoring formula. However, the tool had an
1338additional mode that could control the amount of padding that was inserted;
1339the mode that we used attempted to insert thousands of bytes of padding
1340into a single stack frame! The idea here is, of course, that no overflow
1341attack would ever include hundreds of bytes more than strictly necessary to
1342cause a crash.
1343
1344The primary issue with Fidget is that it's pretty hard to tell that
1345accesses to different members or indexes of a variable are actually
1346accesses to the same variable! It's pretty common for Fidget to patch a
1347binary that uses local array and struct variables liberally, and the
1348resulting patched binary is hilariously broken, crashing if you so much as
1349blow on it. There are a huge number of heuristics we apply to try not to
1350separate different accesses to the same variable, but in the end, variable
1351detection and binary type inference are still open problems. As a result,
1352Fidget also has a "safe mode" that does not try to pad the space in between
1353variables, instead only padding the space between local variables and the
1354saved base pointer and return address.
1355
1356We originally planned to use Fidget in the final round, since it had the
1357potential to disrupt exploits that overflow only from one local variable
1358into an adjacent one, something that none of our final-round techniques can
1359address. However, it was cut from our arsenal at the last minute upon the
1360discovery of a bug in Fidget that was more fundamental than our ability to
1361fix it in the limited time available! Unfortunate...
1362
1363
1364--[ 004.006.002 - CGrex
1365
1366If we know that it's possible for a binary to crash at a given instruction,
1367why don't we just add some code to check if that specific instruction would
1368try to access unmapped or otherwise unusable memory, and if so exit cleanly
1369instead of crashing? This is exactly what CGrex does.
1370
1371Our reassembler was not developed until several weeks before the CGC final
1372event, so for the qualification round CGrex was implemented with a
1373primitive version of what then became the DetourBackend. Once our CRS found
1374a crash, the last good instruction pointer address was sent to CGrex, which
1375produced a patched binary that replaced all crashing instructions with
1376jumps to a special inserted section that used some quirks in some syscalls
1377to determine if the given memory location was readable/writable/executable,
1378and exit cleanly if the instruction would produce a crash.
1379
1380More precisely, CGrex takes, as input, a list of POVs and a CB and it
1381outputs a patched CB "immune" against the provided POVs. CGrex works in
1382five steps:
1383
13841) Run the CGC binary against a given POV using a modified QEMU version
1385 with improved instruction trace logging and able to run CGC binaries.
1386
13872) Detect the instruction pointer where the POV generates a crash (the
1388 "culprit instruction").
1389
13903) Extract the symbolic expression of the memory accesses performed by the
1391 "culprit instruction" (by using Miasm). For instance, if the crashing
1392 instruction is mov eax, [ebx*4+2] the symbolic expression would be
1393 ebx*4+2.
1394
13954) Generate "checking" code that dynamically:
1396 - Compute the memory accesses that the "culprit instruction" is going
1397 to perform.
1398 - Verify that these memory accesses are within allocated memory regions
1399 (and so the "culprit instruction" is not going to crash). To
1400 understand if some memory is allocated or not CGrex "abuses" the
1401 return values of the random and fdwait syscalls.
1402
1403 In particular these syscalls were used by passing as one of the
1404 parameters the value to be checked. The kernel code handling these
1405 functions verifies that, for instance, the pointer were the number of
1406 random bytes returned by random is written is actually pointing to
1407 writable memory and it returns a specific error code if not. CGrex
1408 checks this error code to understand if the tested memory region is
1409 allocated. Special care is taken so that, no matter if the tested
1410 memory location is allocated or not, the injected syscall will not
1411 modify the state of the program.
1412
1413 - If a memory access outside allocated memory is detected, the injected
1414 code just calls exit.
1415
14165) Inject the "checking" code.
1417
1418Steps 1 to 5 are repeated until the binary does not crash anymore with all
1419the provided POVs.
1420
1421
1422
1423--[ 005 - Orchestration
1424
1425 +--------+ +---------+
1426 CGC endpoints | TI API | | IDS tap |
1427 +--------+ +---------+
1428 . .
1429 / \ / \
1430 | |
1431-----------------------------|--------------|------------------------------
1432 | |
1433 Mechanical Phish \ / \ /
1434 ' '
1435 +------------+ +------------+
1436 | Ambassador | |Network Dude|
1437 +------------+ +-+----------+
1438 | |
1439 +------------+ +------------+ | |
1440 | Meister | | Scriba | | |
1441 +-----+------+ +-------+----+ | |
1442 | | | | +--------------------------------+
1443 +--------+--------+ | | | Worker |
1444 | | | | |
1445 _----------_ | | | Poll creator AFL Driller |
1446 ( )<---------+ | | ============ === ======= |
1447 |`----------`|<-------------+ | Tester POV Tester POV Fuzzer |
1448 | |<---------------+ ====== ========== ========== |
1449 | Farnsworth | | Patcherex Colorguard Rex |
1450 ( ) | ========= ========== === |
1451 `----------` +--------------------------------+
1452
1453
1454Designing a fully autonomous system is a challenging feat from an
1455engineering perspective too. In the scope of the CFE, the CRS was required
1456to run without fault for at least 10 hours. Although it was proposed to
1457allow debugging during the CFE, eventually, no human intervention was
1458permitted.
1459
1460To that end, we designed our CRS using a microservice-based approach. Each
1461logical part was split following the KISS principle ("Keep it simple,
1462stupid") and the Unix philosophy ("Do one thing and do it well").
1463
1464Specifically, the separation of logical units allowed us to test and work
1465on every component in complete isolation. We leveraged Docker to run
1466components independently, and Kubernetes to schedule, deploy, and control
1467component instances across all 64 nodes provided to us.
1468
1469
1470--[ 005.001 - Components
1471
1472Several different components of Mechanical Phish interacted closely
1473together during the CRS (see diagram above). In the following, we will
1474briefly talk about the role of each component.
1475
1476* Farnsworth
1477
1478 Farnsworth is a Python-based wrapper around the PostgreSQL database, and
1479 stores all data shared between components: CBs, POVs, crashing inputs,
1480 synchronization structures, etc. In our design, we prohibited any direct
1481 communication between components and required them to talk "through"
1482 Farnsworth. Therefore, Farnsworth was a potential single point of
1483 failure. To reduce the associated risk for the CFE, we paid particular
1484 attention to possible database problems and mitigated them accordingly.
1485
1486* Ambassador
1487
1488 Ambassador was the component that talked to the CGC Team Interface (TI)
1489 to retrieve CBs, obtain feedback, and submit RBs and POVs. In the spirit
1490 of KISS, this component is the only part of Mechanical Phish to
1491 communicate externally and the only source for the ground truth in
1492 respect to the game state.
1493
1494* Meister
1495
1496 Meister coordinated Mechanical Phish. For each component, a component-
1497 specific creator decided which jobs should be run at any point in the
1498 game, based on information obtained through Farnsworth and written by
1499 Ambassador. Consequently, Meister decided which jobs to run based on the
1500 priority information of each job (as specified by the creator) and usage
1501 of the nodes in terms of CPU and memory. Note that, specifically, Meister
1502 and its creators were entirely stateless. At any point, it could crash,
1503 yet it would not kill existing jobs upon automatic restart if they were
1504 still considered important by the creators.
1505
1506* Scriba
1507
1508 An important task of the CRS was to select and submit the POVs and RBs,
1509 respectively. Scriba looked at performance results of exploits and
1510 patches and decided what and when to submit (for more details on the
1511 selection strategy see Section 6 - Strategy). As mentioned previously,
1512 after Scriba decided what and when to submit, Ambassador actually
1513 submitted to the TI (as Ambassador is the only component allowed to
1514 communicate externally).
1515
1516* Network Dude
1517
1518 The Network Dude component received UDP traffic coming from the IDS tap
1519 and stored it into the database via Farnsworth. Since it is required to
1520 receive packets at line-speed, neither parsing nor analysis of the
1521 network data was performed within Network Dude, instead, we relied
1522 different components to process the network traffic.
1523
1524* Worker
1525
1526 Worker was the executor for analysis tasks of the CRS. It wrapped tools
1527 such as angr, Driller, Patcherex in a generic interface to be managed
1528 easily. In fact, every Worker instance referred to an entry in a jobs
1529 queue specifying task arguments and type. Since some of the workers had
1530 to execute CGC DECREE binaries for functionality and performance
1531 evaluation, we included a DECREE virtual machine running on QEMU within a
1532 worker.
1533
1534
1535--[ 005.002 - Dynamic Resource Allocation
1536
1537Another advantage of our architecture design, alongside dependency
1538isolation and ease of deployment, was the possibility to dynamically scale
1539components to meet our needs. Except for the PostgreSQL database and some
1540internal Kubernetes services, all our components could run on any node
1541without limitation.
1542
1543Furthermore, when creating a job, Meister assigned it a priority based on
1544the component and the current game status. For example, crash-generation
1545jobs (Rex) were prioritized lower if an input crash was not considered
1546reliable, or the analysis of a de-fielded CB was considered of no
1547importance at all. Intuitively, all created jobs were sorted by descending
1548values of priority, and scheduled through the Kubernetes API until all
1549nodes' resources (CPU and memory) were saturated. Once all node resources
1550were taken by running jobs, Meister killed jobs with lower priority to
1551accommodate new higher priority jobs, but it did not over-provision.
1552
1553
1554--[ 005.003 - Fail-over
1555
1556Mechanical Phish was required to run without failure for the duration of
1557the CFE, an estimated 10 hours. Furthermore, no debugging sessions were
1558permitted and the CRS was recommended to be resistant to minor hardware
1559failure (or might have risked to "crash and burn").
1560
1561To improve the reliability and resiliency of Mechanical Phish, we took
1562various steps. First, every component, including Ambassador, Meister,
1563Scriba, Network Dude, and Workers, was deployed as a Docker container. All
1564components were designed to be entirely stateless, allowing us to restart
1565them and move them across nodes if necessary.
1566
1567Although components could be terminated abruptly without any significant
1568consequence, some components were critical and were required to be running
1569for Mechanical Phish to function correctly: These were Ambassador, Network
1570Dude, Scriba, and Meister (crashing and recovering is acceptable for these
1571components). Fortunately, Kubernetes provided a way to define
1572always-running instances through DaemonSet and ReplicationController
1573resources. If an instance of such type is terminated or timed out, it is
1574automatically launched on another node (to prevent Kubernetes to be a
1575single point-of-failure, Mechanical Phish was using a highly-available
1576Kubernetes setup with multiple masters and virtual IP addresses for
1577access).
1578
1579* Database
1580
1581 Naturally, the entire system cannot be completely stateless, and a single
1582 stateful component is required, which was Farnsworth. To prevent any
1583 failure of the node running the PostgreSQL Docker containers or the
1584 containers themselves, we leveraged PostgreSQL's built-in master-slave
1585 streaming replication for a resilient system. Specifically, for the CFE,
1586 we ran 5 instances on 5 different physical nodes evenly spread across the
1587 rack, and an additional health-checking monitoring service. The monitor
1588 service itself was run using a ReplicationController resource. If the
1589 master database container would have been considered dead by the monitor,
1590 a slave instance would have been elected as the new master and a
1591 replacement slave would have been created on a healthy node. To prevent
1592 components from failing during database disaster recovery, they accessed
1593 the database in a retry loop with exponential back-off. In turn, it would
1594 have ensured that no data would have been lost during the transition from
1595 a slave to master.
1596
1597* CGC Access Interfaces
1598
1599 The CGC CFE Trials Schedule defined that specific IP addresses were
1600 required to communicate with the CGC API. Given the distributed nature of
1601 our CRS and the recommendation to survive failure, the IP addresses
1602 remained the last single point of failure as specific components needed
1603 to be run on specific physical hosts. Consequently, we used Pacemaker and
1604 Corosync to monitor our components (Ambassador and Network Dude), and
1605 assign the specific IP addresses as virtual IP addresses to a healthy
1606 instance: if a node failed, the address would move to a healthy node.
1607
1608
1609
1610--[ 006 - Strategy
1611
1612---;;;;;;;-----'''''''''``' --- `' .,,ccc$$hcccccc,. `' ,;;!!!'``,;;!!'
1613;;;;,,.,;-------''''''' ,;;!!- .zJ$$$$$$$$$$$$$$$$$$$c,. `' ,;;!!!!' ,;
1614 ```' -;;;!'''''- `.,.. .zJ$$$$$$$$$$$$$$$$$$$$$$$$$$c, `!!'' ,;!!'
1615!!- ' `,;;;;;;;;;;'''''```' ,c$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$c, ;!!'' ,;
1616,;;;!!!!!!!!''``.,;;;;!'`' z$$$$$$$$???"""""'.,,.`"?$$$$$$$$$$$ ``,;;!!!
1617;;.. --''```_..,;;! J$$$$$$??,zcd$$$$$$$$$$$$$$$$$$$$$$$$h ``'``'
1618```''' ,;;''``.,.,;;, ,$$$$$$F,z$$$$$$$$$$$$$$$$$$$c,`""?$$$$$h
1619!!!!;;;;, --`!''''''' $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$h.`"$$$$h .
1620`'''``.,;;;!;;;--;; zF,$$$$$$$$$$?????$$$$$$$$$$$$$?????$$r ;?$$$ $.
1621!;.,..,.````.,;;;; ,$P'J"$$$$$$P" .,c,,.J$$$$$$$$$"',cc,_`?h.`$$$$ $L
1622'``````' .,.. ,$$". $ $$$$P",c$$$$$$$$$$$$$$$$',$$$$$$$$$$ $$$$ $$c,
1623!!!!!!!!!!!!!''' J$',$ $.`$$P c$$$$$$$$$$$$$$$$$$,$$$$$$$$$$$ $$$$ $$$$C
1624 `` J$ ,$P $$ ?$',$$$$???$$$$$$$$$$$$$$$??"""?$$$ <$$$ $$$$$
1625c ;, z$F,$$ `$$ $ ?$" "$$$.?$$$ $$$P c??c, ?$.<$$',$$$$$F
1626$$h. -!> (' $" $F ,F ?$ $ F ,="?$$c,`$$F $$"z$$',$' ,$$P $h.`$ ?$$$$$r
1627$$$$$hc,. ``' J$ $P J$ . $$F L ",,J$$$F <$hc$$ "$L,`??????,J$$$.` z$$$$$
1628$$$$$$$$$$c,'' ?F,$',$F.: $$ c$c,,,,,c,,J$$$$$$$ ?$$$c,,,c$$$$$$F. $$$$$$
1629`"$$$$$$$$$$$c, $$',$$ :: $$$$$$$$F"',$$$$$$$$$$h ?$$$L;;$$$??$$$$ $$$$$$
1630 "?$$$$$$$$$$ $$$$$$ : .`F"$$$$$$$$$$$$""""?"""h $$$$$$$"$,J$$$$ $$$$$'
1631 "?$$$$$$$ $$$$$$.`.` h `$$$$$$$$$$$cccc$$c,zJ$$$$$P' $$$$$P',$$$$P
1632$. `""?$$ $$$$$$$ ` "$c "?$$$$$$$$$$$$??$$$$$$$$" ,J$$$P",J$$$$P
1633.. `" ?$$$$$$h ?$$c.`?$$$$$$$$$' . <$$$$$' ,$$$" ,$$$$$"
1634!!>. . `$$$$$$$h . "$$$c,"$$$$$$$' `' `$$$P ,$$$' ,c$$$$$' ;!
1635```<!!!> `$$$$$$$c "$$$c`?$$$$$ : : $$$ ,$$P' z$$$$$$' ;!!
1636$hc ```' ; `$$$$$$$. ?$$c ?$$$$ .: : $$$ $$F ,J$$$$$$' ;!!
1637.,.. ' `$$$$$$$ "$$h`$$$$ .' ' $$$ ,$$ ,J$$$$$$' !!!
1638????P `$$$$$$L $$$ $$$F :.: J$$P J$F J$$$$$P ;!!
1639-=< ?$$."$$ `$$ ?$$' `' z$$$F $P $$$$$$' !!'
1640cc `$$$c`? ?$.`$$hc, cd$$F ,$' $$$$$$ ;!!
1641 $$$$c `$$c$$$$$$$$$",c$' $$$$$$ `!!
1642 $$$$$ `?$$$$$$$$$$$$P' $$$$$$> ..
1643 $$$$$ `"?$$$$$$$P" $$$$$$L $$c,
1644 !! <$$$$$ zc,`"""', <$$$$$$.`$$$$cc,
1645 !! J$$$$P `$$$$$$$' !' $$$$$$L `$$$$$$h
1646 ;, $$$$$L `! J$$$$$',!! $$$$$$$ `$$$$$$
1647 ' <$$$$$. ! $$$$$$ !! ?$$$$$$ `$$$$$
1648 ,$$$$$$$c `,`???? ;' c,?$$$$' `?$$$
1649 $$$$$$$?? `!;;;;! . `h."?$P `$$$
1650 ,$$$$$$$h. `''' `' `$$$P `?$
1651 $$$$$$$$h `!' `"' `
1652 `$$$$$$$$F !; ! ;,
1653 `$$$$$$$' `!!> `!
1654c, ;, `?$$$$P !!> .
1655$F !!> `""' `!! ;!> <-
1656 The General Strategy of Shellphish
1657
1658The Mechanical Phish was only about three months old when the final event
1659of the Cyber Grand Challenge took place. Like any newborn, its strategic
1660thought processes were not well developed and, unfortunately, the
1661sleep-deprived hackers of Shellphish were haphazard teachers at best. In
1662this section, we describe what amounted to our game strategy for the
1663Mechanical Phish and how the rules of the Cyber Grand Challenge, combined
1664with this strategy, impacted the final result.
1665
1666
1667* Development Strategy
1668
1669
1670The Shellphish CGC team was comprised completely of researchers at the UC
1671Santa Barbara computer security lab. Unfortunately, research labs are
1672extremely disorganized environments. Also unfortunately, as most of us were
1673graduate students, and graduate students need to do research to survive
1674(and eventually graduate), we were fairly limited in the amount of time
1675that we could devote to the CGC. For example, for the CGC Qualification
1676Event, we built our CRS in two and a half weeks. For the final event, we
1677were able to devote a bit more time: on average, each member of the team
1678(the size of which gradually increased from 10 to 13 over the course of the
1679competition) probably spent just under three months on this insanity.
1680
1681One thing that bit us is that we put off true integration of all of the
1682components until the last minute. This led to many last-minute performance
1683issues, some of which we did not sort out before the CFE.
1684
1685
1686* Exploitation Strategy
1687
1688Our exploitation strategy was simple: we attack as soon and as frequently
1689as possible. The only reason that we found to hold back was to avoid
1690letting a victim team steal an exploit. However, there was not enough
1691information in the consensus evaluation to determine whether a team did or
1692did not have an exploit for a given service (and attempting to recover this
1693fact from the network traffic was unreliable), so we decided on a "Total
1694War" approach.
1695
1696
1697* Patching Strategy
1698
1699For every not-failing RB, we submitted the patch considered as the most
1700likely to have a better performance score. Specifically, given the way in
1701which RBs were created, we ranked RBs according to the following list:
1702Optimized Reassembled RB, Reassembled RB, Detouring RB. This choice was
1703motivated by the fact that detouring is slow (as it causes cache flushes
1704due to its propensity to jumping to many code locations), whereas the
1705generated optimized RBs are fast. Of course, we could not always rely on
1706the reassembler (and optimizer) to produce a patch, as these backends had
1707some failure cases.
1708
1709For every patch submitted, the corresponding CS is marked down for a round.
1710Because this can be (and, in the end, was) debilitating to our score, we
1711evaluated many strategies with regards to patching during the months before
1712the CFE. We identified four potential strategies:
1713
1714- Never patch: The simplest strategy was to never patch. This has the
1715 advantage of nullifying the chances of functionality breakages and
1716 avoiding the downtime associated with patching.
1717
1718- Patch when exploited: The optimal strategy would be to patch as soon as
1719 we detect that a CS was being exploited. Unfortunately, detecting when a
1720 CS is exploited is very difficult. For example, while the consensus
1721 evaluation does provide signals that the binaries cause, these signals do
1722 not necessarily correlate to exploitation. Furthermore, replaying
1723 incoming traffic to detect exploitation is non-trivial due to complex
1724 behaviors on the part of the challenge binaries.
1725
1726- Patch after attacking: An alternative strategy is to assume that an
1727 opponent can quickly steal our exploits, and submit a patch immediately
1728 after such exploits are fired. In our latter analysis, we determined that
1729 this would have been the optimal strategy, granting us first place.
1730
1731- Always patch: If working under the assumption that the majority of
1732 challenge sets are exploited, it makes sense to always patch.
1733
1734Most teams in the Cyber Grand Challenge took this decision very seriously.
1735Of course, being the rag-tag group of hackers that we are, we did some
1736fast-and-loose calculations and made a result based on data that turned out
1737to be incorrect. Specifically, we assumed that a similar fraction of the
1738challenges would be exploited as the fraction of challenges crashed during
1739the CQE (about 70%). At the time, this matched up with the percentage of
1740sample CGC binaries, provided by DARPA during sparring partner rounds, that
1741we were exploiting. Running the numbers under this assumption led us to
1742adopt the "always patch" approach:
1743
17441. At the second round of a challenge set's existence, we would check if we
1745 had an exploit ready. If not, we would patch immediately, with the best
1746 available patch (out of the three discussed above). Otherwise, we would
1747 delay for a round so that our exploit had a chance to be run against
1748 other teams.
1749
17502. Once a patch was deployed, we would monitor performance feedback.
1751
17523. If feedback slipped below a set threshold, we would revert to the
1753 original binary and never patch again.
1754
1755In this way, we would patch *once* for every binary. As we discuss later,
1756this turned out to be one of the worst strategies that we could have taken.
1757
1758
1759
1760--[ 007 - Fruits of our Labors
1761
1762In early August, our creation had to fight for its life, on stage, in front
1763of thousands of people. The Mechanical Phish fought well and won third
1764place, netting us $750,000 dollars and cementing our unexpected place as
1765the richest CTF team in the world (with a combined winnings of 1.5 million
1766dollars, Shellphish is the first millionaire CTF team in history!).
1767
1768This is really cool, but it isn't the whole story. The CGC generated
1769enormous amounts of data, and to truly understand what happened in the
1770final event, we need to delve into it. In this section, we'll talk
1771specifically regarding what happened, who achieved what, and how the CGC
1772Final Event played out.
1773
1774For reference throughout this section, the final scores of the CGC Final
1775Event were:
1776
1777 +--------------+------------------+---------+
1778 | Team | CRS Name | Points |
1779 +--------------+------------------+---------+
1780 | ForAllSecure | Mayhem | 270,042 |
1781 | TECHx | Xandra | 262,036 |
1782 | Shellphish | Mechanical Phish | 254,452 |
1783 | DeepRed | Rubeus | 251,759 |
1784 | CodeJitsu | Galactica | 247,534 |
1785 | CSDS | Jima | 246,437 |
1786 | Disekt | Crspy | 236,248 |
1787 +--------------+------------------+---------+
1788
1789The attentive reader will notice that the score of the Mechanical Phish is
1790the only one that is a palindrome.
1791
1792
1793--[ 007.001 - Bugs
1794
1795The CGC was the first time that autonomous systems faced each other in a
1796no-humans-allowed competition. As such, all of the Cyber Reasoning Systems
1797likely faced some amount of bugs during the CFE. The most visible was
1798Mayhem's, which resulted in the system being off-line for most of the
1799second half of the game (although, as we discuss later in this section,
1800that might not have hurt the system as much as one would think). Our
1801system was no different. In looking through the results, we identified a
1802number of bugs that the Mechanical Phish ran into during the CFE:
1803
1804* Multi-CB pipeline assertions
1805
1806We used fuzzing to identify crashes and POV Fuzzing to fuzz those crashes
1807into POVs for challenge sets comprising of multiple binaries.
1808Unfortunately, an accidental assert statement placed in the POV Fuzzing
1809code caused it to opt out of any tasks involving multi-CB challenge sets,
1810disabling our multi-CB exploitation capability.
1811
1812* Network traffic synchronization
1813
1814Due to a bug, the component that scheduled tasks to synchronize and analyze
1815network traffic was set to download *all* recorded network traffic every
1816minute. The volume of this traffic quickly caused it to exceed scheduling
1817timeouts, and Mechanical Phish only analyzed network traffic for the first
181815 rounds of the game.
1819
1820* RB submission race condition
1821
1822Due to a race condition between the component that determined what patches
1823to submit and the component that actually submitted them, we had several
1824instances where we submitted different patched binaries across different
1825rounds, causing multiple rounds of lost uptime.
1826
1827* Scheduling issues
1828
1829Throughout the CFE, Mechanical Phish identified exploitable crashes in over
183040 binaries. However, only 15 exploits were generated. Part, but not all,
1831of this was due to the multi-CB pipeline assertions. It seems that the
1832rest was due to scheduling issues that we have not yet been able to
1833identify.
1834
1835* Slow task spawning
1836
1837Our configuration of Kubernetes was unable to spawn tasks quickly enough to
1838keep up with the job queue. Luckily, we identified this bug a few days
1839before the CFE and put in some workarounds, though we did not have time to
1840fix the root cause. This bug caused us to under-utilize our
1841infrastructure.
1842
1843
1844--[ 007.002 - Pwning Kings
1845
1846Over the course of the CGC Final Event, the Mechanical Phish pwned the most
1847challenges out of the competitors and stole the most flags. This was
1848incredible to see, and is an achievement that we are extremely proud of.
1849Furthermore, the Mechanical Phish stole the most flags even when taking
1850into account only the first 49 rounds, to allow for the fact that Mayhem
1851submitted its last flag on round 49.
1852
1853We've collected the results in a helpful chart, with the teams sorted by
1854the total amount of flags that the teams captured throughout the game.
1855
1856+--------------+-------------------------------+--------------------------+
1857| Team | Flags Captured (first 49/all) | CSes Pwned (first 49/all)|
1858+--------------+-------------------------------+--------------------------+
1859| Shellphish | 206 / 402 | 6 / 15 |
1860| CodeJitsu | 59 / 392 | 3 / 9 |
1861| DeepRed | 154 / 265 | 3 / 6 |
1862| TECHx | 66 / 214 | 2 / 4 |
1863| Disekt | 101 / 210 | 5 / 6 |
1864| ForAllSecure | 185 / 187 | 10 / 11 |
1865| CSDS | 20 / 22 | 1 / 2 |
1866+--------------+-------------------------------+--------------------------+
1867
1868Interestingly, Mayhem exploited an enormous amount of binaries before it
1869went down, but the Mechanical Phish still achieved a higher exploitation
1870score in the rounds that Mayhem was alive. One possibility is that the
1871exploits launched by the Mechanical Phish were more reliable than those of
1872Mayhem. However, its raw exploitation power should not be underestimated:
1873within 49 rounds, before going off the grid, Mayhem managed to exploit 10
1874binaries. While the Mechanical Phish surpassed it over the entire game,
1875this is still quite impressive.
1876
1877
1878--[ 007.003 - Patching Kings
1879
1880To understand how effective our patches were, we calculated the number of
1881flags lost (and the number of CSes on which flags were lost) throughout the
1882game, both for the first 49 rounds (in which Mayhem was online) and for the
1883entire game. As expected, because the Mechanical Phish patched every
1884binary, we found that it was the least-exploited CRS. Specifically, it only
1885leaked flags on 12 challenge sets. The runner-up in this sense (the
1886second-place team, TECHx), leaked flags on 14 binaries.
1887
1888Interestingly, TECHx beat us on the total number of flags leaked. This
1889makes sense -- they likely had some analysis to identify *when* they were
1890being exploited, and patch only then. And, likely, their patches were more
1891effective than our own, leading to a lower number of total flags leaked!
1892
1893The results, sorted by the number of compromised challenges, are:
1894
1895+--------------+-------------------------------+--------------------------+
1896| Team | Defended CS-Rounds (49/all) | CSes Compromised (49/*) |
1897+--------------+-------------------------------+--------------------------+
1898| Shellphish | 29 / 68 | 7 / 12 |
1899| TECHx | 27 / 61 | 7 / 14 |
1900| DeepRed | 32 / 87 | 6 / 15 |
1901| ForAllSecure | 54 / 160 | 7 / 16 |
1902| CodeJitsu | 61 / 104 | 9 / 16 |
1903| Disekt | 66 / 127 | 9 / 17 |
1904| CSDS | 108 / 189 | 9 / 18 |
1905+--------------+-------------------------------+--------------------------+
1906
1907
1908--[ 007.004 - Patching Effectiveness
1909
1910Before the CFE, we tested our patches against the dataset of all CQE
1911binaries released until that point, compiled with many different
1912compilation flags. On this dataset, our chance of breaking a binary, or
1913lowering performance to below 85% (the guesstimated threshold at which we
1914would pull the binary back) was under 2%, and we decided to abandon patch
1915performance/functionality testing. On the actual CFE dataset, we fared
1916worse.
1917
1918The CFE had 82 challenge sets. For these 82 challenge sets, we successfully
1919generated patches for 78. Of these 78, we had to pull back 10 because the
1920patch broke the binary and 7 because the patch lowered the performance of
1921the binary below acceptable levels. This was considerably higher than
1922expected. Furthermore, due to a race condition between the patch submission
1923logic and the component that retrieves the game state, we did end up with
1924situations where we would submit *multiple* patches, thinking that the
1925round had not ended whereas, in reality, it had. In total, we made 107 RCB
1926submissions throughout the game. This was the second-highest amount, with
1927only CodeJitsu submitting more (108).
1928
1929Because very few challenges were exploited during the CFE, this was
1930unequivocally the wrong choice. In total, we lost around 17000 points
1931during the "downtime" rounds after the patch submissions alone.
1932
1933
1934--[ 007.005 - Alternate History Case Studies
1935
1936Hindsight is 20/20. Even though we know, now, that we made the wrong choice
1937regarding our patching strategy, it's still interesting to see what "could
1938have been". In this section, we do that. To better understand the impact of
1939our strategy decisions, we compute scores for several simulated CGC rounds
1940where the Mechanical Phish undertook different strategies, and see what
1941would have happened.
1942
1943It's very important to point out that this is all fantasy. *Every* team can
1944look back and consider things that they might have done differently. The
1945most obvious one is Mayhem: had they avoided crashing, they might have
1946absolutely dominated the competition, rather than relaxedly coasting to
1947victory. However, every other team has other "what if" moments. We explore
1948ours here purely out of curiosity.
1949
1950* Mechanical Phish that never patched
1951
1952To calculate our score in the absence of patching, we recalculated CFE
1953scores, assuming that, any time an exploit would be launched on a CS
1954against *any* team, the exploit would be run against us during that round
1955and all subsequent rounds of that CS being in play. With this calculation,
1956our score would be 267,065, which is 12,613 points higher than the patch
1957strategy that we did choose and would put us in second place by a margin of
1958over 5,000 points.
1959
1960The prize for second place was $1,000,000. Patching at all cost us
1961$250,000!
1962
1963* Mechanical Phish that patched after attacking
1964
1965Similar to the previous strategy, we calculated our score with a patch
1966strategy that would delay patches until *after* we launched exploits on the
1967corresponding CS. For the patches that would have been submitted, we used
1968the same feedback that we received during the CFE itself. With this
1969calculation, our score would be 271,506, which is 17,054 points higher than
1970the patch strategy that we chose and would have put us in first place by a
1971margin of over 1,500 points.
1972
1973The prize for first place was $2,000,000. Patching stupidly cost us
1974$1,250,000 and quite a bit of glory!
1975
1976* Mechanical Phish that didn't do crap
1977
1978We were curious: did we really have to push so hard and trade so much
1979sanity away over the months leading up to the CGC? How would a team that
1980did *nothing* do? That is, if a team connected and then ceased to play,
1981would they fare better or worse than the other players? We ran a similar
1982analysis to the "Never patch" strategy previously (i.e., we counted a CS as
1983exploited for all rounds after its first exploitation against any teams),
1984but this time removed any POV-provided points. In the CFE, this "Team NOP"
1985would have scored 255,678 points, barely *beating* Shellphish and placing
19863rd in the CGC.
1987
1988To be fair, this score calculation does not take into account the fact that
1989teams might have withheld exploits because all opponents were patched
1990against them. However, ForAllSecure patched only 10 binaries, so it does
1991not seem likely that many exploits were held back due to the presence of
1992patches.
1993
1994One way of looking at this is that we could have simply enjoyed life for a
1995year, shown up to the CGC, and walked away with $750,000. Another way of
1996looking at this is that, despite us following the worst possible strategy
1997in regards to patching, the technical aspects of our CRS were good enough
1998to compensate and keep us in the top three positions!
1999
2000
2001--[ 007.006 - Scoring Difficulties
2002
2003Similarly to this being the first time that autonomous systems
2004compete against each other in a no-humans-allowed match, this was also the
2005first time that such a match was *hosted*. The organizing team was up
2006against an astonishing amount of challenges, from hardware to software to
2007politics, and they pulled off an amazing event.
2008
2009However, as in any complex event, some issues are bound to arise. In this
2010case, the problem was that measuring program performance is hard. We found
2011this out while creating our CRS, and DARPA experienced this difficulty
2012during the final event. Specifically, we noticed two anomalies in the
2013scoring data: slight disparities in the initial scoring of challenge sets,
2014and performance "cross-talk" between services.
2015
2016* Initial CS Scoring
2017
2018Patches can only be fielded on round 3 (after being submitted on round 2)
2019of a binary being deployed. However we noticed that our availability scores
2020were lower than our opponents, even on the *first* round of a challenge,
2021when they could not yet be patched. In principle, these should all be the
2022same, as a team has *no* way to influence this performance score. We
2023calculated the average of the first-round CS availability scores, presented
2024in the table below. The scores vary. The difference between the
2025"luckiest" team, regarding their first-round CS score, and the "unluckiest"
2026team was 1.6 percentage points. Unfortunately, Shellphish was that
2027unluckiest team.
2028
2029Since the availability score was used as a multiplier for a team's total
2030score, if the "luckiest" and "unluckiest" had their "luck" swapped, this
2031would compensate for a total score difference of 3.2%. That is a bigger
2032ratio than the difference between second and third place (2.9%), third and
2033fourth place (1.1%), fourth and fifth place (1.7%), and fifth and sixth
2034place (0.4%). The winner (Mayhem) could not have been unseated by these
2035perturbations, but the rest of the playing field could have looked rather
2036different.
2037
2038+--------------+----------------------------------+
2039| Team | Average First Round Availability |
2040+--------------+----------------------------------+
2041| CSDS | 0.9985 |
2042| ForAllSecure | 0.9978 |
2043| Disekt | 0.9975 |
2044| TECHx | 0.9973 |
2045| CodeJitsu | 0.9971 |
2046| DeepRed | 0.9917 |
2047| Shellphish | 0.9824 |
2048+--------------+----------------------------------+
2049
2050* Scoring Cross-talk
2051
2052We also noticed that performance measurements of one challenge seem to
2053influence others. Specifically, when we patched the binary NRFIN_00066 on
2054round 39, we saw the performance of *all* of our other, previously-patched,
2055binaries drop drastically for rounds 40 and 41. This caused us to pull back
2056patches for *all* of our patched binaries, suffering the resulting downtime
2057and decrease in security.
2058
2059Anecdotally, we spoke to two other teams, DeepRed and CodeJitsu, that were
2060affected by such scoring cross-talk issues.
2061
2062
2063
2064--[ 008 - Warez
2065
2066We strongly believe in contributing back to the community. Shortly after
2067qualifying for the Cyber Grand Challenge, we open-sourced our binary
2068analysis engine, angr. Likewise, after the CGC final event, we have
2069released our entire Cyber Reasoning System. The Mechanical Phish is open
2070source, and we hope that others will learn from it and improve it with us.
2071
2072Of course, the fact that we directly benefit from open-source software
2073makes it quite easy for us to support open-source software. Specifically,
2074the Mechanical Phish would not exist without amazing work done by a large
2075number of developers throughout the years. We would like to acknowledge the
2076non-obvious ones (i.e., of course we are all thankful for Linux and vim)
2077here:
2078
2079* AFL (lcamtuf.coredump.cx/afl) - AFL was used as the fuzzer of every
2080 single competitor in the Cyber Grand Challenge, including us. We all owe
2081 lcamtuf a great debt.
2082* PyPy (pypy.org) - PyPy JITed our crappy Python code, often increasing
2083 runtime by a factor of *5*.
2084* VEX (valgrind.org) - VEX, Valgrind's Intermediate Representation of
2085 binary code, provided an excellent base on which to build angr, our
2086 binary analysis engine.
2087* Z3 (github.com/Z3Prover/z3) - angr uses Z3 as its underlying constraint
2088 solver, allowing us to synthesize inputs to drive execution down specific
2089 paths.
2090* Boolector (fmv.jku.at/boolector) - The POVs produced by the Mechanical
2091 Phish required complex reasoning about the relation between input and
2092 output data. To reduce implementation effort, we wanted to use a
2093 constraint solver to handle these relationships. Because Z3 is too huge
2094 and complicated to include in a POV, we ported Boolector to the CGC
2095 platform and included it in every POV the Mechanical Phish threw.
2096* QEMU (qemu.org) - The heavy analyses that angr carries out makes it
2097 considerably slower than qemu, so we used qemu when we needed
2098 lightweight, but fast analyses (such as dynamic tracing).
2099* Unicorn Engine (www.unicorn-engine.org) - angr uses Unicorn Engine to
2100 speed up its heavyweight analyses. Without Unicorn Engine, the number of
2101 exploits that the Mechanical Phish found would have undoubtedly been
2102 lower.
2103* Capstone Engine (www.capstone-engine.org) - We used Capstone Engine to
2104 augment VEX's analysis of x86, in cases when VEX did not provide enough
2105 details. This improved angr's CFG recovery, making our patching more
2106 reliable.
2107* Docker (docker.io) - The individual pieces of our infrastructure ran in
2108 Docker containers, making the components of the Mechanical Phish
2109 well-compartmentalized and easily upgradeable.
2110* Kubernetes (kubernetes.io) - The distribution of docker containers across
2111 our cluster, and the load-balancing and failover of resources, was
2112 handled by kubernetes. In our final setup, the Mechanical Phish was so
2113 resilient that it could probably continue to function in some form even
2114 if the rack was hit with a shotgun blast.
2115* Peewee (https://github.com/coleifer/peewee) - After an initial false
2116 start with a handcrafted HTTP API, we used Peewee as an ORM to our
2117 database.
2118* PostgreSQL (www.postgresql.org) - All of the data that the Mechanical
2119 Phish dealt with, from the binaries to the testcases to the metadata
2120 about crashes and exploits, was stored in a ridiculously-tuned and
2121 absurdly replicated Postgres database, ensuring speed and resilience.
2122
2123As for the Mechanical Phish, this release is pretty huge, involving many
2124components. This section serves as a place to collect them all for your
2125reference. We split them into several categories:
2126
2127--[ 008.001 - The angr Binary Analysis System
2128
2129For completeness, we include the repositories of the angr project, which we
2130open sourced after the CQE. However, we released several additional
2131repositories after the CFE, so we list the whole project here.
2132
2133* Claripy
2134
2135Claripy is our data-model abstraction layer, allowing us to reason about
2136data symbolically, concretely, or in exotic domains such as VSA. It is
2137available at https://github.com/angr/claripy.
2138
2139* CLE.
2140
2141CLE is our binary loader, with support for many different binary formats.
2142It is available at https://github.com/angr/cle.
2143
2144* PyVEX.
2145
2146PyVEX provides a Python interface to the VEX intermediate representation,
2147allowing angr to support multiple architectures. It is available at
2148https://github.com/angr/pyvex.
2149
2150* SimuVEX.
2151
2152SimuVEX is our state model, allowing us to handle requirements of different
2153analyses. It is available at https://github.com/angr/simuvex.
2154
2155* angr.
2156
2157The full-program analysis layer, along with the user-facing API, lives in
2158the angr repository. It is available at https://github.com/angr/angr.
2159
2160* Tracer.
2161
2162This is a collection of code to assist with concolic tracing in angr. It is
2163available at https://github.com/angr/tracer.
2164
2165* Fidget.
2166
2167During the CQE, we used a patching method, called Fidget, that resized and
2168rearranged stack frames to prevent vulnerabilities. It is available at
2169https://github.com/angr/fidget.
2170
2171* Function identifier.
2172
2173We implemented testcase-based function identification, available at
2174https://github.com/angr/identifier.
2175
2176* angrop.
2177
2178Our ROP compiler, allowing us to exploit complex vulnerabilities, is
2179available at https://github.com/salls/angrop.
2180
2181
2182--[ 008.002 - Standalone Exploitation and Patching Tools
2183
2184Some of the software developed for the CRS can be used outside of the
2185context of autonomous security competitions. As such, we have collected it
2186together in a separate place.
2187
2188* Fuzzer.
2189
2190We created a programmatic Python interface to AFL to allow us to use AFL as
2191a module, within or outside of the CRS. It is available at
2192https://github.com/shellphish/fuzzer.
2193
2194* Driller.
2195
2196Our symbolic-assisted fuzzer, which we used as the crash discovery
2197component of the CRS, is available at
2198https://github.com/shellphish/driller.
2199
2200* Rex.
2201
2202The automatic exploitation system of the CRS (and usable as a standalone
2203tool) is available at https://github.com/shellphish/rex.
2204
2205* Patcherex.
2206
2207Our automatic patching engine, which can also be used standalone, is
2208available at https://github.com/shellphish/patcherex.
2209
2210
2211--[ 008.003 - The Mechanical Phish Itself
2212
2213We developed enormous amounts of code to create one of the world's first
2214autonomous security analysis systems. We gathered the code that is specific
2215to the Mechanical Phish under the mechaphish github namespace.
2216
2217
2218* Meister.
2219
2220The core scheduling component for analysis tasks is at
2221https://github.com/mechaphish/meister.
2222
2223* Ambassador.
2224
2225The component that interacted with the CGC TI infrastructure is at
2226https://github.com/mechaphish/ambassador.
2227
2228* Scriba.
2229
2230The component that makes decisions on which POVs and RBs to submit is
2231available at https://github.com/mechaphish/scriba.
2232
2233* Docker workers.
2234
2235Most tasks were run inside docker containers. The glue code that launched
2236these tasks available at https://github.com/mechaphish/worker.
2237
2238* VM workers.
2239
2240Some tasks, such as final POV testing, was done in a virtual machine
2241running DECREE. The scaffolding to do this is available at
2242https://github.com/mechaphish/vm-workers.
2243
2244* Farnsworth.
2245
2246We used a central database as a data store, and used an ORM to access it.
2247The ORM models are available at https://github.com/mechaphish/farnsworth.
2248
2249* POVSim.
2250
2251We ran our POVs in a simulator before testing them on the CGC VM (as the
2252latter is a more expensive process). The simulator is available at
2253https://github.com/mechaphish/povsim.
2254
2255* CGRex.
2256
2257Used only during the CQE, we developed a targeted patching approach that
2258prevents binaries from crashing. It is available at
2259https://github.com/mechaphish/cgrex.
2260
2261* Compilerex.
2262
2263To aid in the compilation of CGC POVs, we collected a set of templates and
2264scripts, available at https://github.com/mechaphish/compilerex.
2265
2266* Boolector.
2267
2268We ported the Boolector SMT solver to the CGC platform so that we could
2269include it in our POVs. It is available at
2270https://github.com/mechaphish/cgc-boolector.
2271
2272* Setup.
2273
2274Our scripts for deploying the CRS are at
2275https://github.com/mechaphish/setup.
2276
2277* Network dude.
2278
2279The CRS component that retrieves network traffic from the TI server is at
2280https://github.com/mechaphish/network_dude.
2281
2282* Patch performance tester.
2283
2284Though it was not ultimately used in the CFE, because performance testing
2285is a very hard problem, our performance tester is at
2286https://github.com/mechaphish/patch_performance.
2287
2288* Virtual competition.
2289
2290We extended the provided mock API of the central server to be able to more
2291thoroughly exercise Mechanical Phish. Our extensions are available at
2292https://github.com/mechaphish/virtual-competitions.
2293
2294* Colorguard.
2295
2296Our Type-2 exploit approach, which uses an embedded constraint solver to
2297recover flag data, is available at
2298https://github.com/mechaphish/colorguard.
2299
2300* MultiAFL.
2301
2302We created a port of AFL that supports analyzing multi-CB challenge sets.
2303It is available at https://github.com/mechaphish/multiafl.
2304
2305* Simulator.
2306
2307To help plan our strategy, we wrote a simulation of the CGC. It is
2308available at https://github.com/mechaphish/simulator.
2309
2310* POV Fuzzing.
2311
2312In addition to Rex, we used a backup strategy of "POV Fuzzing", where a
2313crashing input would be fuzzed to determine relationships that could be
2314used to create a POV. These fuzzers are available at
2315https://github.com/mechaphish/pov_fuzzing.
2316
2317* QEMU CGC port.
2318
2319We ported QEMU to work on DECREE binaries. This port is available at
2320https://github.com/mechaphish/qemu-cgc.
2321
2322
2323
2324--[ 009 - Looking Forward
2325
2326Shellphish is a dynamic team, and we are always looking for the next
2327challenge. What is next? Even we might not know, but we can speculate in
2328this section!
2329
2330
2331* Limitations of the Mechanical Phish
2332
2333The Mechanical Phish is a glorified research prototype, and significant
2334engineering work is needed to bring it to a point where it is usable in the
2335real world. Mostly, this takes the form of implementing the environment
2336model of operating systems other than DECREE. For example, the Mechanical
2337Phish can currently analyze, exploit, and patch Linux binaries, but only if
2338they stick to a very limited number of system calls.
2339
2340We open-sourced the Mechanical Phish in the hopes that work like this can
2341live on after the CGC, and it is our sincere hope that the CRS continues to
2342evolve.
2343
2344
2345* Cyber Grand Challenge 2?
2346
2347As soon as the Cyber Grand Challenge ended, there were discussions about
2348whether or not there would be a CGC2. Generally, DARPA tries to push
2349fundamental advances: they did the self-driving Grand Challenge more than
2350once years, but this seems to be because no teams won it the first time.
2351The fact that they have not done a self-driving Grand Challenge since
2352implies that DARPA is not in the business of running these huge
2353competitions just for the heck of it: they are trying to push research
2354forward.
2355
2356In that sense, it would surprise us if there was a CGC2, on DECREE OS, with
2357the same format as it exists now. For such a game to happen, the community
2358would probably have to organize it themselves. With the reduced barrier to
2359entry (in the form of an open-sourced Mechanical Phish), such a competition
2360could be pretty interesting. Maybe after some more post-CGC recovery, we'll
2361look into it!
2362
2363Of course, we can also sit back and see what ground-breaking concept DARPA
2364comes up with for another Grand Challenge. Maybe there'll be hacking in
2365that one as well.
2366
2367
2368* Shellphish Projects
2369
2370The Mechanical Phish and angr are not Shellphish's only endeavors. We are
2371also very active in CTFs, and one thing to come out of this is the
2372development of various resources to help newbies to CTF. For example, we
2373have put together a "toolset" bundle to help get people started in security
2374with common security tools (github.com/zardus/ctf-tools), and, in the
2375middle of the CGC insanity, ran a series of hack meetings in the university
2376to teach people, by example, how to perform heap meta-data attacks
2377(github.com/shellphish/how2heap). We're continuing down that road, in fact.
2378Monitor our github for our next big thing!
2379`
2380
2381
2382--[ 010 - References
2383
2384[Driller16] Driller: Augmenting Fuzzing Through Selective Symbolic
2385Execution
2386Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang,
2387Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, Giovanni Vigna
2388Proceedings of the Network and Distributed System Security Symposium (NDSS)
2389San Diego, CA February 2016
2390
2391[ArtOfWar16] (State of) The Art of War: Offensive Techniques in Binary
2392Analysis
2393Yan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens, Mario
2394Polino, Andrew Dutcher, John Grosen, Siji Feng, Christophe Hauser,
2395Christopher Kruegel, Giovanni Vigna
2396Proceedings of the IEEE Symposium on Security and Privacy San Jose, CA May
23972016
2398
2399[Ramblr17] Ramblr: Making Reassembly Great Again
2400Ruoyu Wang, Yan Shoshitaishvili, Antonio Bianchi, Aravind Machiry, John
2401Grosen, Paul Grosen, Christopher Kruegel, Giovanni Vigna
2402Proceedings of the Network and Distributed System Security Symposium (NDSS)
2403San Diego, CA February 2017
2404
2405[angr] http://angr.io
2406
2407[Inversion] https://en.wikipedia.org/wiki/Sleep_inversion
2408
2409[CGCFAQ] https://cgc.darpa.mil/CGC_FAQ.pdf