==Phrack Inc.==

               Volume 0x10, Issue 0x46, Phile #0x04 of 0x0f

|=-----------------------------------------------------------------------=|
|=---------------------=[ Cyber Grand Shellphish ]=----------------------=|
|=-----------------------------------------------------------------------=|
|=------------------------=[ Team Shellphish ]=--------------------------=|
|=----------------------=[ [email protected] ]=------------------------=|
|=----------------=[ http://shellphish.net/cgc#team ]=-------------------=|
|=-----------------------------------------------------------------------=|


                   #####
                  #     #   #   #  #####   ######  #####
                  #          # #   #    #  #       #    #
                  #           #    #####   #####   #    #
                  #           #    #    #  #       #####
                  #     #     #    #    #  #       #   #
                   #####      #    #####   ######  #    #

                   #####
                  #     #  #####     ##    #    #  #####
                  #        #    #   #  #   ##   #  #    #
                  #  ####  #    #  #    #  # #  #  #    #
                  #     #  #####   ######  #  # #  #    #
                  #     #  #   #   #    #  #   ##  #    #
                   #####   #    #  #    #  #    #  #####

                                     MM
                                  . MM
                                 =  M
                                M  MM
                               MM  M
                              MM  MM
                             ,M   M
                   MMM  MM+ MM   MM                                      M
               MM  MM  MM   MM   MM  MMMMD                            MMM
          MM+  MM  MM MM    MM  +M   MM :M  MM                       MMM:
        MMMM   MM  MM MM    MM  MM  MMD  M. MM MMM                M  MMM
      MMMMM   =M~  MM MM   MM   MM  MM   M~MM  MM ~MM            MM  MM
   ,MMM       OM   MM MM   MM   MM  MM   M.MM  MM MMM MMMMMM+NM  MM  MM
  MMMMMMMMMM  +MMMMMM MMMN MM   MM  MMMMMM MM  MM MM  MM        MMO  MM
 MMMMMMMMMMMMM MMMMMM MMMN MM   MM  MMMMMN MMMMMM MM  MMMMMMMMM MMMMMMM
MMMM:       MM MM  MM MM   NM:  MM  ?M     MM  MM MMM        MMM MM  MM
,M         MMM MM  MM  MM   MM  MM?  MM    ~MM ~M  MM :MMMMMMMMM MM  MMM
    M M~MMMMMM MM~  MM MM   MM   MM  NM+    MM  MM NMM            ~N  MM
    ,MMMMMMM8   MM  MM :MN  MM   MM+  MMI   NMM                         M
                MMI  MM MMM+ MM~ MMD~ MM



|=-----------------------------------------------------------------------=|
|=----------------------------=[ The Team ]=-----------------------------=|
|=-----------------------------------------------------------------------=|
|=---=[ zardus ]=-----=[ mike_pizza ]=---=[ anton00b ]=----=[ salls ]=---=|
|=-----------------------------------------------------------------------=|
|=---=[ fish ]=---------=[ nebhiros ]=---=[ cao ]=--------=[ donfos ]=---=|
|=-----------------------------------------------------------------------=|
|=---=[ hacopo ]=---------=[ nezorg ]=---=[ rhelmot ]=------=[ paul ]=---=|
|=-----------------------------------------------------------------------=|
|=----------------------------=[ zanardi ]=------------------------------=|
|=-----------------------------------------------------------------------=|




Hacking is often considered more than a skill. In popular culture, hackers
are seen as wizards of sorts, artists with powers to access the
inaccessible, or perform acts that seem impossible. Hacking, like art, has
great people, who are recognized for their skills, but whose abilities
cannot be captured or reproduced. In fact, a single great hacker in a team
is better than a hundred mediocre ones, similar to as none of the paintings
from a hundred mediocre artists can match a painting from van Gogh.

Vulnerability analysis is the science of capturing and reproducing what
some hackers do. Vulnerability analysis studies how one can reason, in a
principled way, about finding and exploiting vulnerabilities in all types
of software or hardware. By developing algorithms and tools to help humans
identify flaws in software, researchers "codify" the knowledge that hackers
use, in an organic way, to analyze systems and find their flaws. The
resulting tools can then be used at scale, and composed to create new
analysis systems.

This scientific process has generated a number of useful tools, such as
static analysis tools, fuzzers, and symbolic execution frameworks. However,
these tools codify only a subset of the skills of a hacker, and they are
still used only to augment the abilities of humans.

One approach to push the codification of what human hackers do, is to take
the hackers out of the equation. This is precisely what the DARPA Cyber
Grand Challenge was set out to do.

The DARPA Cyber Grand Challenge (CGC) was designed as a Capture The Flag
(CTF) competition among autonomous systems without any humans being
involved. During the competition, Cyber Reasoning Systems (CRSs) would find
vulnerabilities in binaries, exploit them, and generate patches to protect
them from attacks, without any human involvement at all.

The separation between human and machine is key, as it forces the
participants to codify, in algorithms, the techniques used for both attack
and defense. Although the competition was only a first step toward
capturing the art of hacking, it was an important one: for the first time,
completely autonomous systems were hacking one another with code, and not
human intuition, driving the discovery of flaws in complex software
systems.


Shellphish is a team that was founded by Professor Giovanni Vigna at UC
Santa Barbara in 2005 to participate in the DEF CON CTF with his graduate
students. Since then, Shellphish has evolved to include dozens of
individuals (graduate students - now professors elsewhere, undergraduate
students, visitors, their friends, etc.) who are somewhat connected by the
Security Lab at UC Santa Barbara, but who are now spread all across the
world. Nonetheless, Shellphish has never lost its "hackademic" background
and its interest in the science behind hacking. Participation in many CTF
competitions sparked novel research ideas, which, in addition to
publications, resulted in tools, which, in turn, were put to good use
during CTF competitions.

Given the academic focus of Shellphish, it is no surprise that the DARPA
Cyber Grand Challenge seemed like a great opportunity to put the research
carried out at the UC Santa Barbara SecLab to work. Unfortunately, when the
call for participation for the funded track came out, the lab was (as
usual) busy with a great number of research projects and research
endeavors, and there were simply no cycles left to dedicate to this effort.
However, when the call for the qualification round that was open to anybody
who wanted to throw their hat in the ring was announced, a group of
dedicated students from the SecLab decided to participate, entering the
competition as team Shellphish.

With only a few weeks to spare, the Shellphish team put together a
prototype of a system that automatically identifies crashes in binaries
using a novel composition of fuzzing and symbolic execution.
Unsurprisingly, the system was largely unstable and crashed more than the
binaries it was supposed to crash.  Yet, it performed well and Shellphish
was one of the seven teams (out of more than a hundred participants) that
qualified for the final event. Since Shellphish was not initially funded by
DARPA through the funded track, it received a $750,000 award to fund the
creation of the autonomous system that would participate in the final
competition.

The following few months focused mostly on basic research, which resulted
in a number of interesting scientific results in the field of binary
analysis [Driller16, ArtOfWar16], and to the dramatic improvement of angr
[angr], an open-source framework created at the UC Santa Barbara SecLab to
support the analysis of binaries.

Eventually, the pressure to create a fully autonomous system increased to
the point that academic research had to be traded for system-building.
During the several months preceding the final competition event, all the
energy of the Shellphish team focused on creating a solid system that could
be resilient to failure, perform at scale, and be able not only to crash
binaries, but also to generate reliable exploits and patches.

After gruesome months of Sushi-fueled work that lead to severe Circadian
rhythm sleep disorder [Inversion] in many of the team's members, the
Mechanical Phish Cyber Reasoning System was born. Mechanical Phish is a
highly-available, distributed system that can identify flaws in DECREE
binaries, generate exploits (called Proofs Of Vulnerability, or POVs), and
patched binaries, without human intervention. In a way, Mechanical Phish
represents a codification of some of the hacking skills of Shellphish.

Mechanical Phish participated in the final event, held in Las Vegas on
August 4th, in conjunction with DEF CON, and placed third, winning a
$750,000 prize. As a team, we were ecstatic: our system performed more
successful exploits than any other CRS, and it was exploited on fewer
challenges than any other CRS. Of course, in typical Shellphish style, the
game strategy is where we lost points, but the technical aspects of our CRS
were some of the best. 

We decided to make our system completely open-source (at the time of
writing, Shellphish is the only team that decided to do so), so that others
can build upon and improve what we put together.

The rest of this article describes the design of our system, how it
performed, and the many lessons learned in designing, implementing, and
deploying Mechanical Phish.



--[ Contents

    1 - The Cyber Grand Challenge

    2 - Finding Bugs

    3 - Exploiting

    4 - Patching

    5 - Orchestration

    6 - Strategy

    7 - Results

    8 - Warez

    9 - Looking Forward



--[ 001 - The Cyber Grand Challenge

The Cyber Grand Challenge was run by DARPA, and DARPA is a government
agency. As such, the amount of rules, regulations, errata, and so forth was
considerably out of the range with which we were familiar. For example, the
Frequently Asked Questions document alone, which became the CGC Bible of
sorts, reached 68 dense pages by the time the final event came around;
roughly the size of a small novella. This novella held much crucial
information, and this crucial information had to be absorbed by the team,
digested, and regurgitated into the squawking maw of the Mechanical Phish.


--[ 001.001 - Game Format

The CGC Final Event took the form of a more-or-less traditional
attack-defense CTF. This means that each team had to attack, and defend
against, each other team. Counter to A&D CTF tradition, and similar to the
setup of several editions of the UCSB iCTF, exploits could not be run
directly against opponents, but had to be submitted to the organizers.
Likewise, patches could not be directly installed (i.e., with something
like scp), but had to be submitted through the central API, termed the
"Team Interface" (TI) by DARPA. This allowed DARPA to maintain full control
over when and how often attacks were launched, and how patches were
evaluated.

The CGC was divided into rounds (specifically, there were 95 rounds in the
final event) of at least 5 minutes each. Each round, the TI specified the
currently-active challenges. A challenge could be introduced at any point,
up to a maximum of 30 concurrently active challenges, and was guaranteed to
remain live for a minimum of 10 rounds.

All teams would start with the same binaries for a challenge. Each round,
teams could submit patches for their instances of the challenge binaries,
exploits for the opponents' instances, and network rules to filter traffic.
Submitted exploits would go "live" on the round *after* the one during
which they were submitted, while submitted patches and network rules would
go live 2 rounds after. Submitting a patch, causes that team to incur one
round of downtime for that challenge, in which opponents can download the
patched binary. Patched binaries were visible by opponents to allow them
to exploit incomplete patches.


--[ 001.002 - Game Scoring

The CGC employed a scoring algorithm that had serious implications for the
strategies that were viable for teams to adopt. Each team would be scored
on a per-round basis, and a team's final score was the sum of all of their
round scores. A team's round score was, in turn, the sum of their
"Challenge Binary Round Scores" for that round. This CB Round Score was the
real crux of the matter.

A CB Round Score was calculated for every Challenge Binary to be a simple
multiplication of:

- Availability: this was a measure of the performance overhead and
  functionality impact introduced by a patch. The performance and
  functionality scores each ranged from 0 (broken) to 100 (perfect), and
  the availability score was the minimum of these numbers.
- Security: this number was 2 if the Challenge Binary was secure (i.e.,
  it had not been exploited by any competitor that round), and 1
  otherwise (if it was exploited by at least one competitor).
- Evaluation: this number ranged from 1.0 to 2.0, based on how many
  opponents the team was hitting with their exploits (if any) for this
  challenge binary. For example, if an exploit was succeeding against 2 of
  the 6 opponents, this number would be 1.33.

The round after a patch was submitted or an IDS rule was updated for a
challenge binary, that challenge binary's availability score would be set
to 0 and no exploits would be scheduled (either by the patching team or
against the patching team) for that round.

On the surface, this seems like a simple formula. However, there were
several complications:

- DARPA did not disclose the formula used to calculate the performance or
  functionality scores prior to the CFE. While this was presumably done to
  avoid letting teams "game the system", it led to an astonishing amount of
  uncertainty regarding patching. Teams knew that they had some "free"
  overhead (20% for the file size, and 5% each for runtime overhead and
  memory overhead), but did not know how additional overhead would be
  penalized.
- The runtime overhead included overhead introduced by the network IDS as
  it matched submitted network rules. This overhead was fundamentally
  unmeasurable before the game. During the CFE, it turned out that the
  overhead introduced by network rules from one service could actually
  influence overhead of *other* services. All this uncertainty kept all but
  two teams from using the network IDS during the CFE.
- The memory and runtime overhead was astonishingly hard to measure. As we
  discuss later, local measurements were so unreliable that we actually
  decided not to test our own patches for performance during the CFE, but
  optimized the techniques as much as possible beforehand and relied on the
  TI feedback for already-submitted patches. As we'll also discuss, DARPA
  themselves had some trouble keeping the measurements constant, with
  measurements between teams (for identical, unpatched binaries) varying by
  significant amounts.

Overall, the performance scoring was both a strength and weakness of the
game. Because of the ease with which exploits can be "broken" by simple
patches, it was critical to have some patch dis-incentives. However, the
measurement of such patches is a very hard problem, and led to some chaos.


--[ 001.003 - Visibility

With the CGC, DARPA pioneered something called the "Consensus Evaluation".
This had many implications for many parts of the game, but the biggest one
was a slight change to the "visibility" of certain aspects of the game to
the different teams. In this section, we'll detail what information was
available to competitors during the game.

All interaction with the game was done via the CGC API (what DARPA called
the Team Interface, or TI). The TI provided the following information:

- The Challenges: all teams could retrieve the challenges that were "in
  play" at any given moment.

- Patched Binaries: all teams could retrieve the patched binaries of *all*
  opponents. This prevented opponents from deploying "chump" patches that
  relied on simple security through obscurity.

- IDS rules: all teams could retrieve the IDS rules that were being fielded
  by their opponents.

- Availability impacts: a team could see the runtime overhead, memory
  overhead, and functionality impact of their submitted patches.

- Crashes: a team could see what signals their binaries crashed with as a
  result of processing network traffic. This could give hints for whether
  or not exploits were being thrown against a challenge binary.

- Network Traffic: a team could get most of the network traffic, including
  all exploits and most of the functionality polls (DARPA reserved the
  right to keep some of them secret).

- POV Feedback: a team could get the results of their own exploits against
  other teams.

- Round scores: teams could get the overall round scores of all
  competitors.

This level of visibility is different than your "average" CTF.
Specifically, the big difference is that the patches submitted by the Cyber
Reasoning Systems were made available to opponents. In theory, this would
allow opponents to analyze, and try to bypass, a CRS' patches. In practice,
as we discussed in the Patching section, patched binaries were too
"dangerous" to analyze. Teams were allowed to add anti-reversing code, and,
in our experience, it was easy to find ways to crash analysis tools, or
"clog" them, causing them to slow down or use extra resources. We did not
dare to run our heavier analysis on the patched binaries, and we are not
aware of any team that did. Instead, our heavy analysis was run strictly on
the original, unpatched binaries, and the patched binaries were run through
a quick analysis that would fix up memory offsets and so forth in the case
of "chump" patches.


--[ 001.004 - Practice

Full autonomy is difficult to achieve. To mitigate some of this difficulty,
DARPA provided CGC practice sessions through a "sparring partner". In the
months leading up to the final event, the sparring partner would connect to
our Cyber Reasoning System at random, unannounced times and begin a game.

The presence of the sparring partner was immensely helpful in debugging
interactions with the API. However, the unannounced nature of these events
meant that it was rarely possible to be ready for this debugging.
Additionally, since DARPA only had one sparring partner setup, and teams
had to take turns interacting with it, the sparring partner sessions were
very short (generally, about 30 minutes, or 5 rounds). The reduced length
of these sessions made it more difficult to truly stress-test the systems,
and several teams showed signs of failure due to overload during the final
event itself.

We mostly used the practice round to test the difference between DARPA's
calculated overhead from our estimated one. This allowed us to get a vague
idea of how DARPA calculated overhead, and tailor our patching techniques
accordingly.


--[ 001.005 - DECREE OS

The binaries that made up the Cyber Grand Challenge's challenges were not
standard Linux binaries. Instead, they were binaries for an OS, called
DECREE, that was created specifically for the Cyber Grand Challenge. This
OS was extremely simple: there were 7 system calls, and no persistence
(i.e., filesystem storage, etc). The DECREE syscalls are:

1. terminate: the equivalent of exit()
2. transmit: the equivalent of send()
3. receive: the equivalent of recv()
4. fdwait: the equivalent of select()
5. allocate: the equivalent of mmap()
6. deallocate: the equivalent of munmap()
7. random: a system call that would generate random data

The hardware platform for the binaries was 32-bit x86. Challenge authors
were not allowed to include inline assembly code, only code which was
produced by clang or included in a library provided by DARPA. The provided
math library included instructions such as floating point logarithms and
trigonometric operations. All other code had to be produced directly by the
compiler (clang).

This simple environment model allowed competitors to focus on their program
analysis techniques, rather than the implementation details that go along
with support complex OS environments. The DECREE OS was, in the opinion of
many of us, the biggest thing that made the CGC possible with humanity's
current level of technology.




--[ 002 - Finding Bugs


  -----------------------------------------
  |               Driller                 |
  |                                       |
  | ++++++++++++++        ++++++++++++++  |
  | + angr       + =====> + AFL        +  |
  | +            +        +            +  |
  | + Symbolic   +        + Genetic    +  |
  | + Tracing    + <===== + Fuzzing    +  |
  | ++++++++++++++        ++++++++++++++  |
  |                                       |
  -----------------------------------------



There are a few things we considered when we thought about how we wanted to
find bugs in the Cyber Grand Challenge. Firstly, we will need to craft
exploits using the bugs we find. As a result, we need to use techniques
which generate inputs that trigger the bugs, not just point out that there
could be a bug. Secondly, the bugs might be guarded by specific checks such
as matching a command argument, password or checksum. Lastly, the programs
which we need to analyze might be large, so we need techniques which scale
well.

The automated bug finding techniques can be divided into three groups:
static analysis, fuzzing, and symbolic execution. Static analysis is not
too useful as it doesn't generate inputs which actually trigger the bug.
Symbolic execution is great for generating inputs which pass difficult
checks, however, it scales poorly in large programs. Fuzzing can handle
fairly large programs, but struggles to get past difficult checks. The
solution we came up with is to combine fuzzing and symbolic execution,
into a state-of-the-art guided fuzzer, called Driller. Driller uses a
mutational fuzzer to exercise components within the binary, and then uses
symbolic execution to find inputs which can reach a different component.

* Fuzzing

Driller leverages a popular off-the-shelf fuzzer, American Fuzzy Lop. AFL
uses instrumentation to identify the transitions that a particular input
exercises when it is passed to the program. These transitions are tuples
of source and destination basic blocks in the control flow graph. New
transition tuples often represent functionality, or code paths, that has
not been exercised before; logically, these inputs containing new
transition tuples are prioritized by the fuzzer.

To facilitate the instrumentation, we use a fork of QEMU, which enables the
execution of DECREE binaries. Some minor modifications were made to the
fuzzer and to the emulation of DECREE binaries to enable faster fuzzing as
well as finding deeper bugs:

- De-randomization
    Randomization by the program interferes with the fuzzer's evaluation
    of inputs - an input that hits an interesting transition with one
    random seed, may not hit it with a different random seed. Removing
    randomness allows the fuzzer to explore sections of the program which
    may be guarded by randomness such as "challenge-response" exchanges.
    During fuzzing, we ensure that the flag page is initialized with a
    constant seed, and the random system call always returns constant
    values so there is no randomness in the system. The Exploitation
    component of our CRS, is responsible for handling the removal of
    randomness.

- Double Receive Failure
    The system call receive fails after the input has been completely read
    in by the program and the file descriptor is now closed. Any binary
    which does not check the error codes for this failure may enter an
    infinite loop, which slows down the fuzzer dramatically. To prevent
    this behavior, if the receive system call fails twice because the
    end-of-file has been reached, the program is terminated immediately.

- At-Receive Fork Server
    AFL employs a fork server, which forks the program for each execution
    of an input to speed up fuzzing by avoiding costly system calls and
    initialization. Given that the binary has been de-randomized as
    described above, all executions of it must be identical up until the
    first call to receive, which is the first point in which non-constant
    data may enter the system. This allows the fork-server to be moved
    from the entry of the program, to right before the first call to
    receive. If there is any costly initialization of globals and data
    structures, this modification speeds up the fuzzing process greatly.

* Network Seeds

Network traffic can contain valuable seeds which can be given to the
fuzzer to greatly increase the fuzzing effectiveness. Functionality tests
exercise deep functionality within the program and network traffic from
exploits may exercise the particular functionality which is buggy. To
generate seeds from the traffic, each input to the program is run with the
instrumentation from QEMU to identify if it hits any transitions which
have not been found before. If this condition is met, the input is
considered interesting and is added as a seed for the fuzzer.

* Adding Symbolic Execution

Although symbolic execution is slow and costly, it is extremely powerful.
Symbolic execution uses a constraint solver to generate specific inputs
which will exercise a given path in the binary. As such, it can produce
the inputs which pass a difficult check such as a password, a magic
number, or even a checksum. However, an approach based entirely on
symbolic execution will quickly succumb to path explosion, as the number
of paths through the binary exponentially increases with each branch.

Driller mitigates the path-explosion problem by only tracing the paths
which the fuzzer, AFL, finds interesting. This set of paths is often small
enough that tracing the inputs in it is feasible within the time
constraints of the competition. During each symbolic trace, Driller
attempts to identify transitions that have not yet been exercised by the
fuzzer, and, if possible, it generates an input which will deviate from
the trace and take a new transition instead. These new inputs are fed back
into the fuzzer, where they will be further mutated to continue exercising
deeper paths, following the new transitions.

* Symbolic Tracing

To ensure that the symbolic trace using angr's concolic execution engine
is identical to the native execution trace, we use pre-constraining. In
pre-constrained execution, each byte of input is constrained to match the
original byte of input that was used by the fuzzer. When a branch is
reached that would lead to a new transition, the pre-constraints are
removed and then the solver is queried for an input which reaches the new
transition. Pre-constraining also has the benefit of greatly improving
execution time, because one does not need to perform expensive solves to
determine the locations of reads and writes to memory because all
variables have only one possible value.





--[ 003 - The Exploiting Component


                    Crashes                            Inputs
                      ||                                 ||
                      ||                                 ||
           ========================                      ||
           ||                    ||                      ||
           ||                    ||                      ||
           \/                    \/                      \/
  --------------------   --------------------   --------------------
  | REX              |   | PovFuzzer        |   | Colorguard       |
  |                  |   |                  |   |                  |
  | ++++++++++++++   |   | ++++++++++++++   |   | ++++++++++++++   |
  | + Advanced   +   |   | + Fuzzing    +   |   | + Finding    +   |
  | + AEG        +   |   | + For        +   |   | + Leaks      +   |
  | +            +   |   | + Exploits   +   |   | +            +   |
  | ++++++++++++++   |   | ++++++++++++++   |   | ++++++++++++++   |
  |                  |   |                  |   |                  |
  |      ...         |   |                  |   |                  |
  --------------------   --------------------   --------------------
           ||                    ||                      ||
           ================================================
                                 ||
                                 \/
                                POVs


* Exploitation

In the Cyber Grand Challenge, stealing flags is a little different than
it is in ordinary Capture the Flag games. Instead of reading a secret
"flag" file and submitting the contents to the organizers, an exploit is
demonstrated by submitting a Proof of Vulnerability (POV), which the
organizers will run.

A POV is a binary program, which will communicate with the opponent's
binary and "exploit" it. There are two ways in which a POV can be
considered successful:
- Type 1: Cause a segmentation fault where the instruction pointer and one
          additional register have values which were previously negotiated
          with the competition infrastructure. Must control at least
          20 bits of EIP as well as 20 bits of another register.
- Type 2: Read 4 contiguous bytes from the secret flag data. The flag data
          is located at 0x4347c000-0x4347cfff and is randomly initialized
          by the kernel.

Different types of vulnerabilities might lend themselves to a specific
type of POV. For example, a vulnerability where the user can control the
address passed to puts() might only be usable as a Type 2 POV. On the
other hand, a stack-based buffer overflow can clearly be used to create a
Type 1 exploit simply by setting a register and EIP, but it can also be
used to create a Type 2 exploit by using Return Oriented Programming or by
jumping to shellcode which prints data from the flag page.

* Overview

The basic design for Mechanical Phish's automatic exploitation is to take
crashes, triage them, and modify them to create exploits. Mechanical Phish
does not need to understand the root cause of the bug, instead it only
needs to identify what registers and memory it controls at crash time, and
how those values can be set to produce a POV. We created two systems which
are designed to go from crashes to exploits.

- PovFuzzer
    Executes the binary repeatedly, slightly modifying the input,
    tracking the relationship between input bytes and registers at the
    crash point. This method is fast, but cannot handle complex cases.

- Rex
    Symbolically executes the input, tracking formulas for all registers
    and memory values. Applies "techniques" on this state, such as
    jumping to shellcode, and return oriented programming to create a POV.

Now this design was missing one important thing. For some challenges the
buggy functionality does not result in a crash! Consider a buffer
over-read, where it reads passed the end of the buffer. This may not cause
a crash, but if any copy of flag data is there, then it will print the
secret data. To handle this, we added a third component.

- Colorguard
    Traces the execution of a binary with a particular input and
    checks for flag data being leaked out. If flag data is leaked, then
    it uses the symbolic formulas to determine if it can produce a valid
    POV.


--[ 003.001 - PovFuzzer

The PovFuzzer takes a crash and repeatedly changes a single byte at a time
until it can determine which bytes control the EIP as well as another
register. Then a Type 1 POV can be constructed which simply chooses the
input bytes that correspond to the negotiated EIP and register values,
inserts the bytes in the payload, and sends it to the target program.

For crashes which occur on a dereference of controlled data, the PovFuzzer
chooses bytes that cause the dereference to point to the flag page, in the
hope that flag data will be printed out. After pointing the dereference at
the flag page, it executes the program to check if flag data is printed
out. If so, it constructs a Type 2 POV using that input.

The PovFuzzer has many limitations. It cannot handle cases where register
values are computed in a non-trivial manner, such as through
multiplication.  Furthermore it cannot handle construction of more complex
exploits such as jumping to shellcode, or where it needs to replay a random
value printed by the target program. Even so, it is useful for a couple
reasons.  Firstly, it is much faster than Rex, because it only needs to
execute the program concretely. Secondly, although we don't like to admit
it, angr might still have occasional bugs, and the PovFuzzer is a good
fallback in those cases as it doesn't rely on angr.


--[ 003.002 - Rex

The general design of Rex is to take a crashing payload, use angr to
symbolically trace the program with the crashing payload, collecting
symbolic formulas for all memory and input along the way. Once we hit the
point where the program crashes, we stop tracing, but use the constraint
solver to pick values that either make the crash a valid POV, or avoid the
crash to explore further. There are many ways we can choose to constrain
the values at this point, each of which tries to exploit the program in a
different way. These methods of exploiting the program are called
"techniques".

One quick thing to note here is that we include a constraint solver in our
POVs. By including a constraint solver we can simply add all of the
constraints collected during tracing and exploitation into the POV and
then ask the constraint solver at runtime for a solution that matches the
negotiated values. The constraint solver, as well as angr, operates on
bit-vectors enabling the techniques to be bit-precise.

Here we will describe the various "techniques" which Rex employs.

- Circumstantial Exploit
    This technique is applicable for ip-overwrite crashes and is the
    simplest technique. It determines if at least 20 bits of the
    instruction pointer and one register are controlled by user input. If
    so, an exploit is constructed that will negotiate the register and ip
    values and then solve the constraints to determine the user input
    that sets them correctly.

- Shellcode Exploit
    Also only applicable to ip-overwrites, this technique will search for
    regions of executable memory that are controlled by user input. The
    largest region of controlled executable memory is chosen and the
    memory there is constrained to be a nop-sled followed by shellcode to
    either prove a type-1 or type-2 vulnerability. A shellcode exploit
    can function even if the user input only controls the ip value, and
    not an additional register.

- ROP Exploit
    Although the stack is executable by default, opponents might employ
    additional protections that prevent jumping to shellcode, such as
    remapping the stack, primitive Address Randomization or even some
    form of Control Flow Integrity. Return Oriented Programming (ROP) can
    bypass incomplete defenses and still prove vulnerabilities for
    opponents that employ them. It is applicable for ip-overwrite crashes
    as long as there is user data near the stack pointer, or the binary
    contains a gadget to pivot the stack pointer to the user data.

- Arbitrary Read - Point to Flag
    A crash that occurs when the program tries to dereference user-
    controlled data is considered an "arbitrary read". In some cases, by
    simply constraining the address that will be dereferenced to point at
    flag data, the flag data will be leaked to stdout, enabling the
    creation of a type-2 exploit. Point to Flag constrains the input to
    point at the flag page, or at any copy of flag data in memory, then
    uses Colorguard to determine if the new input causes an exploitable
    leak.

- Arbitrary Read/Write - Exploration
    In some cases, the dereference of user-controlled data can lead to a
    more powerful exploit later. For example, a vtable overwrite will
    first appear as an arbitrary read, but if that memory address points
    to user data, then the read will result in a controlled ip. To
    explore arbitrary reads/writes for a better crash, the address of the
    read or write is constrained to point to user data, then the input is
    re-traced as a new crash.

- Write-What-Where
     If the input from the user controls both the data being written and
     the address to which it is written, we want to identify valuable
     targets to overwrite. This is done by symbolically exploring the
     crash, to identify values in memory that influence the instruction
     pointer, such as return addresses or function pointers. Other
     valuable targets are pointers that are used to print data;
     overwriting these can lead to type-2 exploits.


--[ 003.003 - Colorguard

As explained above, there are some challenges which include
vulnerabilities that can leak flag data, but do not cause a crash. One
challenge here is that it is difficult to detect when a leak occurs. You
can check if any 4 bytes of output data are contained in the flag page,
but this will have false positives while fuzzing, and it will miss any
case where the data is not leaked directly. The challenge authors seem to
prefer to xor the data or otherwise obfuscate the leak, maybe to prevent
such a method.

To accurately detect these leaks we chose to trace the inputs
symbolically, using angr. However, symbolic tracing is far too slow to run
on every input that the fuzzer generates. Instead, we only perform the
symbolic tracing on the inputs which the fuzzer considers "interesting".
The hope here is that the leak causing inputs have a new transition, or
number of loops which is unique, and that the fuzzer will consider it
interesting. There are definitely cases where this doesn't work, but it's
a fairly good heuristic for reducing the number of traces.

In an effort to further combat the slowness of symbolic execution,
Colorguard takes advantage of angr's concrete emulation mode. Since no
modification of the input has to be made if a flag leak is discovered, our
input is made entirely concrete, with the only symbolic data being that
from the flag page. This allows us to only execute symbolically
those basic blocks that touch the secret flag page contents.

Colorguard traces the entire input concretely and collects the symbolic
expression for the data that is printed to stdout. The expression is
parsed to identify any four consecutive bytes of the flag page that are
contained in the output. For each set of bytes, the solver is queried to
check if we can compute the values of the bytes only from the output data.
If so, then an exploit is crafted which solves for these four bytes after
receiving the output from the program execution.

One caveat here is that challenges may use many bytes of the flag page as
a random seed. In these cases we might see every byte of the flag page as
part of the expression for stdout. Querying the constraint solver for
every one of these consecutive four byte sequences is prohibitively slow,
so it is necessary to pre-filter such expressions. Colorguard does this
pre-filter during the trace by replacing any expression containing more
than 13 flag bytes with a new symbolic variable. The new symbolic variable
is not considered a potential leak. The number 13 was arbitrarily chosen
as it was high enough to still detect all of the leaks we had examples for,
but low enough that checking for leaks was still fast.


--[ 003.004 - Challenge Response

A common pattern that still needs to be considered is where the binary
randomly chooses a value, outputs it, and then requires the user to input
that value or something computed from the random value. For example, the
binary prints "Solve the equation: 6329*4291" and then the user must input
"27157739". To handle these patterns in the exploit, we identify any
constraints that involve both user input and random data. Once identified,
we check the output that has been printed up to that point if it contains
the random data. If so, then we have identified a challenge-response. We
will include the output as a variable in the constraints that are passed
to the exploit, and then read from stdout, adding constraints that the
output bytes match what is received during the exploit. Then the solver
can be queried to generate the input necessary for the correct "response".



--[ 004 - The Patching Component: Patcherex

       Original
       Binary (CB)
         ||
         ||
         ||===============================================
         ||                                             ||
         ||                                             ||
         \/                                             \/
  --------------------   --------------------   --------------------
  | TECHNIQUES       |   | PATCHES          |   | BACKENDS         |
  |                  |   |                  |   |                  |
  | ++++++++++++++   |   |                  |   |                  |
  | + Return     +   |   |   - AddROData()  |   |                  |
  | + Pointer    + --------> - AddCode()    |   |  +++++++++++++++ |
  | + Encryption +   |   |   - ...          |   |  + Detour      + |
  | ++++++++++++++   |   |                  |   |  + Backend     + |
  |                  |   |                  |   |  +             + |
  | ++++++++++++++   |   |                  |   |  +++++++++++++++ |
  | + Transmit   +   |   |   - InsertCode() |   |                  |
  | + Protection + --------> - AddRWData()  |==>|       OR         |
  | +            +   |   |   - ...          |   |                  |
  | ++++++++++++++   |   |                  |   |  +++++++++++++++ |
  |                  |   |                  |   |  + Reassembler + |
  | ++++++++++++++   |   |                  |   |  + Backend     + |
  | +            +   |   |   - AddCode()    |   |  +             + |
  | + Backdoor   + --------> - AddRWData()  |   |  +++++++++++++++ |
  | +            +   |   |   - ...          |   |                  |
  | ++++++++++++++   |   |                  |   |                  |
  |                  |   |                  |   |                  |
  |      ...         |   |                  |   |                  |
  --------------------   --------------------   --------------------
                                                         ||
                                                         ||
                                                         \/
                                                      Replacement
                                                      Binary (RB)


Patcherex, which is built on top of angr, is the central patching system of
Mechanical Phish. As illustrated in the overview image, Patcherex is
composed of three major components: techniques, patches, and patching
backends.

* Techniques

A technique is the implementation of a high-level patching strategy. A set
of patches (described below) with respect to a binary are generated after
applying a technique on it. Currently Patcherex implements three different
types of techniques:

- Generic binary hardening techniques, including Return Pointer Encryption,
  Transmit Protection, Simple Control-Flow Integrity, Indirect Control-Flow
  Integrity, Generic Pointer Encryption;
- Techniques aiming at preventing rivals from analyzing or stealing our
  patches, including backdoors, anti-analysis techniques, etc.;
- Optimization techniques that make binaries more performant, including
  constant propagation, dead assignment elimination, and redundant stack
  variables removal.

* Patches

A Patch is a low-level description of how a fix or an improvement should be
made on the target binary. Patcherex defines a variety types of patches to
perform tasks ranging from code/data insertion/removal to segment altering.

* Backends

A backend takes patches generated from one or more techniques, and applies
them on the target binary. Two backends available in Patcherex:

- ReassemblerBackend: this backend takes a binary, completely disassembles
  the entire binary, symbolizes all code and data references among code and
  data regions, and then generate an assembly file. It then apply patches
  on the assembly file, and calls an external assembler (it was clang for
  CGC) to reassemble the patched assembly file to the final binary.
- DetourBackend: this backend acts as a fallback to the
  ReassemblerBackend. It performs in-line hooking and detouring to apply
  patches.


--[ 004.001 - Patching Techniques

In this section, we describe all techniques we implemented in Patcherex.

Obviously we tried to implement techniques that will prevent exploitation
of the given CBs, by making their bugs not exploitable. In some cases,
however, our techniques do not render the bugs completely unexploitable,
but they still force an attacker to adapt its exploits to our RBs. For
instance, some techniques introduce differences in the memory layout
between our generated RB and the original CB an attacker may have used to
develop its exploit. In addition, we try to prevent attackers from adapting
exploits to our RB by adding anti-analysis techniques inside our generated
binaries. Furthermore, although we put a significant effort in minimizing
the speed and memory impact of our patches, it is often impossible to have
performance impact lower than 5% (a CB score starts to be lowered when it
has more than 5% of speed or memory overhead). For this reason we decided
to "optimize" the produced RB, as we will explain later.

--[ 004.001.001 - Binary Hardening Techniques

We implemented some techniques for generic binary hardening. Those general
hardening techniques, although not extremely complex, turned out to be very
useful in the CFE.

Vulnerability-targeted hardening (targeted patching) was also planned
initially. However, due to lack of manpower and fear for deploying
replacement CBs too many times for the same challenge, we did not fully
implement or test our targeted patching strategies.

* Return Pointer Encryption

This technique was designed to protect from classical stack buffer
overflows, which typically give an attacker control over an overwritten
saved return pointer. Our defense mechanism "encrypts" every return pointer
saved on the stack when a function is called, by modifying the function's
prologue. The encrypted pointer is then "decrypted" before every ret
instruction terminating the same function. For encryption and decryption we
simply xor'ed the saved return pointer with a nonce (randomly generated
during program's startup). Since the added code is executed every time a
function is called, we take special care in minimizing the performance
impact of this technique.

First of all, this technique is not applied in functions determined as
safe. We classify a function as safe if one of these three conditions is
true:

- The function does not access any stack buffer.
- The function is called by more than 5 different functions. In this case,
  we assume that the function is some standard "utility" function, and it
  is unlikely that it contains bugs. Even if it contains bugs, the
  performance cost of patching such a function is usually too high.
- The function is called by printf or free. Again, we assume that library
  functions are unlikely to contain bugs. These common library functions
  are identified by running the functions with test input and output pairs.
  This function identification functionality is offered by a separate
  component (the "Function identifier" mentioned in the "Warez" Section).

To further improve the performance, the code snippet that encrypts and
decrypts the saved return pointer uses, when possible, a "free" register to
perform its computations. This avoids saving and restoring the value of a
register every time the injected code is executed. We identify free
registers (at a specific code location) by looking for registers in which a
write operation always happens before any read operation. This analysis is
performed by exploring the binary's CFG in a depth-first manner, starting
from the analyzed code location (i.e., the location where the code
encrypting/decrypting the return pointer is injected).

Finally, to avoid negatively impacting the functionality of the binary, we
did not patch functions in which the CFG reconstruction algorithm has
problems in identifying the prologue and the epilogues. In fact, in those
cases, it could happen that if an epilogue of the analyzed function is not
identified, the encrypted return address will not be decrypted when that
epilogue is reached, and consequently the program will use the
still-encrypted return pointer on the stack as the return target. This
scenario typically happens when the compiler applies tail-call
optimizations by inserting jmp instructions at the end of a function.

* Transmit Protection

As a defense mechanism against Type 2 exploits, we inject code around the
transmit syscall so that a binary is forbidden from transmitting any 4
contiguous bytes of the flag page. The injected code uses an array to
keep track of the last transmitted bytes so that it can identify cases
in which bytes of the flag page are leaked one at a time.

* Simple Control-Flow Integrity

To protect indirect control flow instructions (e.g., call eax, jmp ebx), we
inject, before any instruction of this kind, code that checks specific
properties of the target address (i.e., the address which the instruction
pointer will be after the call or jump). The specific checks are:

- The target address must be an allocated address (to prevent an attacker
from using the indirect control-flow instruction to directly perform a
Type 1 attack). To do so, we try to read from the target address, so that
if the address does not point to an allocated region the program will crash
before the instruction pointer is modified. This prevents simple Type 1
exploits, because the attacker must control at least 20 bits of the
instruction pointer, and it is unlikely (but not impossible) that the
negotiated value will end up inside an allocated memory region.

- The target address must be inside the memory range where the binary's
code is typically loaded (for simplicity, we consider a "potential code"
address to be any below 0x4347c000). To avoid breaking programs that use
dynamically allocated code we do not perform this check if we statically
detect that the analyzed program calls the allocate syscall in a way which
will create additional executable memory.

- The target address is not a pop instruction. As a partial mitigation
against ROP attacks, we dynamically check if the target of indirect calls
is a pop instruction, and terminate the program otherwise.

* Uninitialized Data Cleaning

For each function, we identify all of the instructions that read and write
to stack variables, and the stack offset that is accessed. If there is any
path through the CFG such that a stack variable is read before it is
written, then we consider it possible that there is an uninitialized data
usage. For each variable that is detected in an uninitialized data usage,
we zero that variable by adding stack cleaning code at the beginning of the
function.

* Stack Base Address Randomization

On program's startup we add a random value (which can assume any 16-byte
aligned value between 16 and 1024) to the stack pointer address. This adds
indeterminism to the position of the stack, hindering any exploit making
assumptions on the program's stack layout.

* malloc Protection

To interfere with exploitation of heap overflows, if we are able to
identify a malloc-like function inside the analyzed CB, we slightly modify
its behavior. In particular, we change the amount of bytes allocated by a
small, pseudo-random, value.

* printf Protection

For every printf-like function identified, such as printf, snprintf, etc.,
we ensure that the function is not used to perform a "format string"
attack. Specifically, if the format string parameter is neither in the
binary's read-only memory nor a string already present in the binary, we
stop the execution of the binary if:
- The format string parameter contains a meta character (e.g., "%").
- The format string parameter points to the flag page.


--[ 004.001.002 - Adversarial Techniques

Certain techniques are introduced to prevent rivals from analyzing, or even
running our RBs in a controlled environment, while leaving those RBs still
able to run in the real game environment. These techniques are presented in
this section.

* Anti-analysis

We add some code, executed before the original entry point of the binary,
to interfere with analyses that other teams could perform on our patched
binary. Specifically, we add code to:
- Detect if the binary is executed using QEMU or PIN. To do so, we probe
  the implementation of different aspects that are difficult to emulate
  correctly, such as segment registers, transmission of partially allocated
  memory regions, syscall error codes values in case of "double failure".
  In addition, we add some code triggering a previously unknown
  implementation bug in QEMU, making it stall. Specifically, during the
  development of our CRS, we found that QEMU, when using user-mode
  emulation, does not correctly handle taking the square root of an
  "un-normal" floating point number, that is, a nonzero 80-bit float whose
  explicit integer bit (the highest bit of the mantissa) is zero. When this
  happens, QEMU will hang forever. Because of this anti-QEMU patch, some of
  our RBs broke the live visualization during the CFE public event.
- Interfere with symbolic execution engines. Our adversarial code contains
  self-modifying code designed to be extremely hard to simulate correctly
  and efficiently by a symbolic execution engine. In addition, some added
  code is specifically designed to trigger "path explosion" conditions.
- Interfere with automatic exploitation systems. We add code to transmit
  the flag page to file descriptor 2 (stderr). Although data transmitted to
  this file descriptor is not sent to a CRS interacting with a binary, an
  opponent could mistakenly assume that any contiguous 4 bytes transmitted
  from the flag page constitutes a Type 2 exploit and thus fielding a POV
  trying to leverage this "fake" leak. In addition, we inject "fake
  backdoor" code. This code is triggered if a CRS sends a specific 4-byte
  sequence. When triggered, it reads from the CRS 8 bytes used to set the
  program instruction pointer and the value of a register. For this reason,
  this code looks like easily exploitable to create a Type 1 POV, however
  the read values are xor'ed with a random value, before being used to set
  the instruction pointer and the register, making this code
  non-exploitable.

In addition, to counteract an adversary fielding one of our own patched
binaries as its own patched binary, we inject a backdoor in every fielded
patched binary. This backdoor can be used by our CRS to exploit the patched
binary we generate, but it is designed to be extremely hard to be exploited
from other teams' CRSs. The backdoor is triggered when a specific 4-byte
sequence is received. To detect this, the function wrapping the receive
syscall is modified to keep track of the first 4 bytes a program receives.
Once triggered, the backdoor sends to the CRS a "challenge" C (which is a
19-bit value), and the CRS responds with a response R (a 64-bit value).
Then, the backdoor code checks if the following condition is true:
first_32_bits_of(SHA1(pad(R,160))) == pad(C,32), where pad(A,N) is a
function padding the input value A up to N bits by adding zeros.

The challenge can be easily solved by pre-computing all the possible
responses, but it is impossible for an opponent's POV to compute a solution
for the challenge within the game-imposed 10-second timeout.


--[ 004.001.003 - Optimization Techniques

Performance is a vital concern of our patching strategy. While we stress
the necessity of optimizing all our patching techniques, some overhead
cannot be avoided. From analyzing binaries collected from CQE and CFE
samples, we noticed that most of them are compiled with O0, i.e., without
optimization enabled. We do not know why organizers decided not to optimize
most of the provided challenges, but we speculated that this may have been
decided to leave room for optimizations and patching.

It is well-known that O0 and O1 binaries can have a huge difference in
execution time. Fortunately, some of the optimization methods used in O1
are not that difficult to perform directly on binaries. Further, angr
provides all necessary data-flow analysis techniques, which makes the whole
optimization development easier. Finally, with the help of the
ReassemblerBackend, we can easily fully remove instructions that we want to
get rid of, without having to replace them with nops. Therefore, we
implemented some basic in-line binary optimization techniques in order to
optimize O0 binaries in CFE, which are described below.


- Constant Propagation. We propagate constants used as immediates in each
  instruction, and eliminate unnecessary mov instructions in assembly code.
- Dead Assignment Elimination. Many unnecessary assignments occur in
  unoptimized code. For example, in unoptimized code, when a function reads
  arguments passed from the stack, it will always make a copy of the
  argument into the local stack frame, without checking if the argument is
  modified or not in the local function. We perform a conservative check
  for cases where a parameter is not modified at all in a function and the
  copy-to-local-frame is unnecessary. In this case, the copy-to-local
  instruction is eliminated, and all references to the corresponding
  variable on the local stack frame are altered to reference the original
  parameter on the previous stack frame. Theoretically, we may break the
  locality, but we noticed some improvement in performance in our off-line
  tests.
- Redundant Stack Variable Removal. In unoptimized code, registers are not
  allocated optimally, and usually many registers end up not being used. We
  perform a data-flow analysis on individual functions, and try to replace
  stack variables with registers. This technique works well with variables
  accessed within tight loops. Empirically speaking, this technique
  contributes the most to the overall performance gain we have seen during
  testing.

Thanks to these optimizations, our patches often had *zero* overall
performance overhead.

--[ 004.002 - Patches

The techniques presented in the previous section return, as an output,
lists of patches. In Patcherex, a patch is a single modification to a
binary.

The most important types of patches are:

- InsertCodePatch: add some code that is going to be executed before an
  instruction at a specific address.
- AddEntryPointPatch: add some code that is going to be executed before the
  original entry point of the binary.
- AddCodePatch: add some code that other patches can use.
- AddRWData: add some readable and writable data that other patches can
  use.
- AddROData: add some read-only data that other patches can use.

Patches can refer to each other using an easy symbol system. For instance,
code injected by an InsertCodePatch can contain an instruction like call
check_function. In this example, this call instruction will call the code
contained in an InsertCodePatch named check_function.


--[ 004.003 - Backends

We implemented two different backends to inject different patches. The
DetourBackend adds patches by inserting jumps inside the original code,
whereas the ReassemblerBacked adds code by disassembling and then
reassembling the original binary. The DetourBackend generates bigger (thus
using more memory) and slower binaries (and in some rare cases it cannot
insert some patches), however it is slightly more reliable than the
ReassemblerBackend (i.e., it breaks functionality in slightly less
binaries).

* DetourBackend

This backend adds patches by inserting jumps inside the original code. To
avoid breaking the original binary, information from the CFG of the binary
is used to avoid placing the added jmp instruction in-between two basic
blocks. The added jmp instruction points to an added code segment in which
first the code overwritten by the added jmp and then the injected code is
executed. At the end of the injected code, an additional jmp instruction
brings the instruction pointer back to its normal flow.

In some cases, when the basic block that needs to be modified is too small,
this backend may fail applying an InsertCodePatch. This requires special
handling, since patches are not, in the general case, independent (a patch
may require the presence of another patch not to break the functionality of
a binary). For this reason, when this backend fails in inserting a patch,
the patches "depending" from the failed one are not applied to the binary.

* ReassemblerBackend

ReassemblerBackend fully disassembles the target binary, applies all
patches on the generated assembly, and then assembles the assembly back
into a new binary. This is the primary patching backend we used in the CFE.
Being able to fully reassemble binaries greatly reduces the performance hit
introduced by our patches, and enables binary optimization, which improves
the performance of our RBs even further. Also, reassembling usually changes
base addresses and function offsets, which achieves a certain level of
"security by obscurity" -- rivals will have to analyze our RBs if they want
to properly adapt their code-reusing and data-reusing attacks.

We provide an empirical solution for binary reassembling that works on
almost every binary from CQE and CFE samples. The technique is open-sourced
as a component in angr, and, after the CGC competition, it has been
extended to work with generic x86 and x86-64 Linux binaries.

A detailed explanation as well as evaluation of this technique is published
as an academic paper [Ramblr17].

--[ 004.004 - Patching Strategy

We used Patcherex to generate, for every CB, three different Replacement
Binaries (RBs):

- Detouring RB: this RB was generated by applying, using the DetourBackend,
  all the patches generated by the hardening and adversarial techniques
  presented previously.
- Reassembled RB: this RB was generated by applying the same patches used
  by the Detouring RB, but using the ReassemblerBackend instead of the
  DetourBackend.
- Optimized Reassembled RB: this RB was generated as the Reassembled one,
  but, in addition all the patches generated by the optimization techniques
  were added.

These three patched RBs have been listed in order of decreasing performance
overhead and decreasing reliability. In other words, the Detouring RB is
the most reliable (i.e., it has the smallest probability of having broken
functionality), but it has the highest performance overhead with respect to
the original unpatched binary. On the contrary the Optimized Reassembled RB
is the most likely to have broken functionality, but it has a lower
performance impact.


--[ 004.005 - Replacement Binary Evaluation

* Pre-CFE Evaluation

During initial stages of Patcherex development, testing of the RBs was done
by an in-house developed component called Tester. Internally, Tester uses
cb-test, a utility provided by DARPA for testing a binary with
pre-generated input and output pairs, called polls. We made modifications
to cb-test, which enabled the testing of a binary and its associated IDS
rules on a single machine, whereas the default cb-test needs 3-machines to
test a binary with IDS rules.

Tester can perform both performance and functionality testing of the
provided binary using the pre-generated polls for the corresponding binary
using its Makefile. For functionality testing, given a binary, we randomly
pick 10 polls and check that the binary passes all the polls. For
performance testing, we compute the relative overhead of the provided
binary against the unpatched one using all the polls. However, there was
huge discrepancy (~10%) between the performance overhead computed by us and
that provided during sparring partner sessions for the same binaries.
Moreover, during the sparring partner sessions, we also noticed that
performance numbers were different across different rounds for the same
binaries. Because of these discrepancies and to be conservative, for every
patching strategy, we computed the performance overhead as the maximum
overhead across all rounds of sparring partner sessions during which RBs
with corresponding patching strategy are fielded.

During internal testing we used all the available binaries publicly
released on GitHub (some of which were designed for the CQE event, whereas
others were sample CFE challenges). To further extend our test cases, we
recompiled all the binaries using different compilation flags influencing
the optimization level used by the compiler. In fact, we noticed that
heavily optimized binaries (e.g., -O3), were significantly harder to
analyze and to patch without breaking functionality. Specifically, we used
the following compilations flags: -O0, -Os, -Oz, -O1, -O2, -O3, -Ofast.
Interestingly, we noticed that some of the binaries, when recompiled with
specific compilation flags, failed to work even when not patched.

During the final stages of Patcherex development, we noticed that almost
all generated RBs never failed the functionality and that the performance
overhead was reasonable except for a few binaries. This, combined with the
discrepancy inherent in performance testing, led us not to use any in-depth
testing of our replacement binaries during the CFE.

* CFE Evaluation

For every RB successfully generated, Patcherex first performs a quick test
of their functionality. The test is designed to spot RBs that are broken by
the patching strategy.  In particular, Patcherex only checks that every
generated RB does not crash when provided with a small test set of
hardcoded input strings ("B", "\n", "\n\n\n\n\n\n", etc.)

We decided to perform only a minimal tests of the functionality because of
for performance and reliability considerations.

--[ 004.006 - Qualification Round Approaches

It is worth mentioning that for the CGC qualification round, the rules were
very different from the final round. Between this and the fact that our
analysis tools were not yet mature it was necessary for us to approach
patching very differently from the final round approaches previously
described.

In the qualification round, the only criteria for "exploitation" was a
crash. If you could crash a binary, it meant that you could exploit it, and
if your binary could crash, it meant that you were vulnerable. Furthermore,
the qualification scoring formula was such that your "defense" score, i.e.
how many vulnerabilities your patch protected against, was a global
multiplier for your score between zero and one. This meant that if you
didn't submit a patch for a binary, or if your patch failed to protect
against any of the vulnerabilities, you received zero points for that
challenge, regardless of how well you were able to exploit it.

This is such an unconventional scoring system that when we analyzed the
(publicly available) patches produced by other teams for the qualification
round, we found that at least one qualifying team had a patching strategy
such that whenever they discovered a crash, they patched the crashing
instruction to simply call the exit syscall. This is technically not a
crash, so the teams that did this did in fact receive defense points for
the challenges, and accordingly did in fact receive a non-negligible score
for effectively stubbing out any vaguely problematic part of the binary.

Our approaches were slightly more nuanced! There were two techniques we
developed for the qualification round, one "general" technique, meaning
that it could be applied to a program without any knowledge of the
vulnerabilities in a binary, and one "targeted" technique, meaning that it
was applied based on our CRS' knowledge of a vulnerability. Each of the
techniques could produce several candidate patched binaries, so we had to
choose which one to submit in the end - our choice was based on some
rudimentary testing to try to ascertain if the binary could still crash,
and if not, to assess the performance impact of the patch.

It is important to notice for CQE, the patched binaries were tested by the
organizers against a fixed set of pre-generated exploits. For this reason,
our patched binaries just had to prevent to be exploited when run against
exploit developed for the original, unpatched, version of the program. In
other words, the attacker had no way to adapt its exploits to our patches
and so "security trough obscurity" techniques were extremely effective
during the qualification event.


--[ 004.006.001 - Fidget

Our "general" patching technique for CQE was a tool called Fidget. Fidget
was developed the summer prior to the announcement of the CGC for use in
attack-defense CTFs. Its basic intuition is that the development of an
attack makes a large number of very strong assumptions about the internal
memory layout of a program, so in many cases simply tweaking the layout of
stack variables is a reliable security-through-obscurity technique.

At the time of the CQE, Fidget was a tool capable of expanding function
stack frames, putting unused space in between local variables stored on the
stack. This is clearly not sufficient to prevent crashes, as is necessary
for the strange qualification scoring formula. However, the tool had an
additional mode that could control the amount of padding that was inserted;
the mode that we used attempted to insert thousands of bytes of padding
into a single stack frame! The idea here is, of course, that no overflow
attack would ever include hundreds of bytes more than strictly necessary to
cause a crash.

The primary issue with Fidget is that it's pretty hard to tell that
accesses to different members or indexes of a variable are actually
accesses to the same variable! It's pretty common for Fidget to patch a
binary that uses local array and struct variables liberally, and the
resulting patched binary is hilariously broken, crashing if you so much as
blow on it. There are a huge number of heuristics we apply to try not to
separate different accesses to the same variable, but in the end, variable
detection and binary type inference are still open problems. As a result,
Fidget also has a "safe mode" that does not try to pad the space in between
variables, instead only padding the space between local variables and the
saved base pointer and return address.

We originally planned to use Fidget in the final round, since it had the
potential to disrupt exploits that overflow only from one local variable
into an adjacent one, something that none of our final-round techniques can
address. However, it was cut from our arsenal at the last minute upon the
discovery of a bug in Fidget that was more fundamental than our ability to
fix it in the limited time available! Unfortunate...


--[ 004.006.002 - CGrex

If we know that it's possible for a binary to crash at a given instruction,
why don't we just add some code to check if that specific instruction would
try to access unmapped or otherwise unusable memory, and if so exit cleanly
instead of crashing? This is exactly what CGrex does.

Our reassembler was not developed until several weeks before the CGC final
event, so for the qualification round CGrex was implemented with a
primitive version of what then became the DetourBackend. Once our CRS found
a crash, the last good instruction pointer address was sent to CGrex, which
produced a patched binary that replaced all crashing instructions with
jumps to a special inserted section that used some quirks in some syscalls
to determine if the given memory location was readable/writable/executable,
and exit cleanly if the instruction would produce a crash.

More precisely, CGrex takes, as input, a list of POVs and a CB and it
outputs a patched CB "immune" against the provided POVs. CGrex works in
five steps:

1) Run the CGC binary against a given POV using a modified QEMU version
   with improved instruction trace logging and able to run CGC binaries.

2) Detect the instruction pointer where the POV generates a crash (the
   "culprit instruction").

3) Extract the symbolic expression of the memory accesses performed by the
   "culprit instruction" (by using Miasm). For instance, if the crashing
   instruction is mov eax, [ebx*4+2] the symbolic expression would be
   ebx*4+2.

4) Generate "checking" code that dynamically:
    - Compute the memory accesses that the "culprit instruction" is going
      to perform.
    - Verify that these memory accesses are within allocated memory regions
      (and so the "culprit instruction" is not going to crash). To
      understand if some memory is allocated or not CGrex "abuses" the
      return values of the random and fdwait syscalls.

      In particular these syscalls were used by passing as one of the
      parameters the value to be checked. The kernel code handling these
      functions verifies that, for instance, the pointer were the number of
      random bytes returned by random is written is actually pointing to
      writable memory and it returns a specific error code if not. CGrex
      checks this error code to understand if the tested memory region is
      allocated. Special care is taken so that, no matter if the tested
      memory location is allocated or not, the injected syscall will not
      modify the state of the program.

    - If a memory access outside allocated memory is detected, the injected
      code just calls exit.

5) Inject the "checking" code.

Steps 1 to 5 are repeated until the binary does not crash anymore with all
the provided POVs.



--[ 005 - Orchestration

                         +--------+    +---------+
 CGC endpoints           | TI API |    | IDS tap |
                         +--------+    +---------+
                             .              .
                            / \            / \
                             |              |
-----------------------------|--------------|------------------------------
                             |              |
 Mechanical Phish           \ /            \ /
                             '              '
                    +------------+  +------------+
                    | Ambassador |  |Network Dude|
                    +------------+  +-+----------+
                                 |   |
 +------------+  +------------+  |   |
 |  Meister   |  |   Scriba   |  |   |
 +-----+------+  +-------+----+  |   |
       |                 |       |   | +--------------------------------+
       +--------+--------+       |   | |             Worker             |
                |                |   | |                                |
          _----------_           |   | | Poll creator    AFL    Driller |
         (            )<---------+   | | ============    ===    ======= |
         |`----------`|<-------------+ | Tester  POV Tester  POV Fuzzer |
         |            |<---------------+ ======  ==========  ========== |
         | Farnsworth |                | Patcherex    Colorguard    Rex |
         (            )                | =========    ==========    === |
          `----------`                 +--------------------------------+


Designing a fully autonomous system is a challenging feat from an
engineering perspective too. In the scope of the CFE, the CRS was required
to run without fault for at least 10 hours. Although it was proposed to
allow debugging during the CFE, eventually, no human intervention was
permitted.

To that end, we designed our CRS using a microservice-based approach. Each
logical part was split following the KISS principle ("Keep it simple,
stupid") and the Unix philosophy ("Do one thing and do it well").

Specifically, the separation of logical units allowed us to test and work
on every component in complete isolation. We leveraged Docker to run
components independently, and Kubernetes to schedule, deploy, and control
component instances across all 64 nodes provided to us.


--[ 005.001 - Components

Several different components of Mechanical Phish interacted closely
together during the CRS (see diagram above). In the following, we will
briefly talk about the role of each component.

* Farnsworth

  Farnsworth is a Python-based wrapper around the PostgreSQL database, and
  stores all data shared between components: CBs, POVs, crashing inputs,
  synchronization structures, etc. In our design, we prohibited any direct
  communication between components and required them to talk "through"
  Farnsworth. Therefore, Farnsworth was a potential single point of
  failure. To reduce the associated risk for the CFE, we paid particular
  attention to possible database problems and mitigated them accordingly.

* Ambassador

  Ambassador was the component that talked to the CGC Team Interface (TI)
  to retrieve CBs, obtain feedback, and submit RBs and POVs. In the spirit
  of KISS, this component is the only part of Mechanical Phish to
  communicate externally and the only source for the ground truth in
  respect to the game state.

* Meister

  Meister coordinated Mechanical Phish. For each component, a component-
  specific creator decided which jobs should be run at any point in the
  game, based on information obtained through Farnsworth and written by
  Ambassador.  Consequently, Meister decided which jobs to run based on the
  priority information of each job (as specified by the creator) and usage
  of the nodes in terms of CPU and memory. Note that, specifically, Meister
  and its creators were entirely stateless. At any point, it could crash,
  yet it would not kill existing jobs upon automatic restart if they were
  still considered important by the creators.

* Scriba

  An important task of the CRS was to select and submit the POVs and RBs,
  respectively. Scriba looked at performance results of exploits and
  patches and decided what and when to submit (for more details on the
  selection strategy see Section 6 - Strategy). As mentioned previously,
  after Scriba decided what and when to submit, Ambassador actually
  submitted to the TI (as Ambassador is the only component allowed to
  communicate externally).

* Network Dude

  The Network Dude component received UDP traffic coming from the IDS tap
  and stored it into the database via Farnsworth. Since it is required to
  receive packets at line-speed, neither parsing nor analysis of the
  network data was performed within Network Dude, instead, we relied
  different components to process the network traffic.

* Worker

  Worker was the executor for analysis tasks of the CRS. It wrapped tools
  such as angr, Driller, Patcherex in a generic interface to be managed
  easily.  In fact, every Worker instance referred to an entry in a jobs
  queue specifying task arguments and type. Since some of the workers had
  to execute CGC DECREE binaries for functionality and performance
  evaluation, we included a DECREE virtual machine running on QEMU within a
  worker.


--[ 005.002 - Dynamic Resource Allocation

Another advantage of our architecture design, alongside dependency
isolation and ease of deployment, was the possibility to dynamically scale
components to meet our needs. Except for the PostgreSQL database and some
internal Kubernetes services, all our components could run on any node
without limitation.

Furthermore, when creating a job, Meister assigned it a priority based on
the component and the current game status. For example, crash-generation
jobs (Rex) were prioritized lower if an input crash was not considered
reliable, or the analysis of a de-fielded CB was considered of no
importance at all.  Intuitively, all created jobs were sorted by descending
values of priority, and scheduled through the Kubernetes API until all
nodes' resources (CPU and memory) were saturated. Once all node resources
were taken by running jobs, Meister killed jobs with lower priority to
accommodate new higher priority jobs, but it did not over-provision.


--[ 005.003 - Fail-over

Mechanical Phish was required to run without failure for the duration of
the CFE, an estimated 10 hours. Furthermore, no debugging sessions were
permitted and the CRS was recommended to be resistant to minor hardware
failure (or might have risked to "crash and burn").

To improve the reliability and resiliency of Mechanical Phish, we took
various steps. First, every component, including Ambassador, Meister,
Scriba, Network Dude, and Workers, was deployed as a Docker container. All
components were designed to be entirely stateless, allowing us to restart
them and move them across nodes if necessary.

Although components could be terminated abruptly without any significant
consequence, some components were critical and were required to be running
for Mechanical Phish to function correctly: These were Ambassador, Network
Dude, Scriba, and Meister (crashing and recovering is acceptable for these
components). Fortunately, Kubernetes provided a way to define
always-running instances through DaemonSet and ReplicationController
resources. If an instance of such type is terminated or timed out, it is
automatically launched on another node (to prevent Kubernetes to be a
single point-of-failure, Mechanical Phish was using a highly-available
Kubernetes setup with multiple masters and virtual IP addresses for
access).

* Database

  Naturally, the entire system cannot be completely stateless, and a single
  stateful component is required, which was Farnsworth.  To prevent any
  failure of the node running the PostgreSQL Docker containers or the
  containers themselves, we leveraged PostgreSQL's built-in master-slave
  streaming replication for a resilient system.  Specifically, for the CFE,
  we ran 5 instances on 5 different physical nodes evenly spread across the
  rack, and an additional health-checking monitoring service. The monitor
  service itself was run using a ReplicationController resource. If the
  master database container would have been considered dead by the monitor,
  a slave instance would have been elected as the new master and a
  replacement slave would have been created on a healthy node. To prevent
  components from failing during database disaster recovery, they accessed
  the database in a retry loop with exponential back-off. In turn, it would
  have ensured that no data would have been lost during the transition from
  a slave to master.

* CGC Access Interfaces

  The CGC CFE Trials Schedule defined that specific IP addresses were
  required to communicate with the CGC API. Given the distributed nature of
  our CRS and the recommendation to survive failure, the IP addresses
  remained the last single point of failure as specific components needed
  to be run on specific physical hosts. Consequently, we used Pacemaker and
  Corosync to monitor our components (Ambassador and Network Dude), and
  assign the specific IP addresses as virtual IP addresses to a healthy
  instance: if a node failed, the address would move to a healthy node.



--[ 006 - Strategy

---;;;;;;;-----'''''''''``'  --- `'  .,,ccc$$hcccccc,.  `' ,;;!!!'``,;;!!'
;;;;,,.,;-------''''''' ,;;!!-    .zJ$$$$$$$$$$$$$$$$$$$c,. `' ,;;!!!!' ,;
  ```'    -;;;!'''''-  `.,..   .zJ$$$$$$$$$$$$$$$$$$$$$$$$$$c, `!!'' ,;!!'
!!-  ' `,;;;;;;;;;;'''''```' ,c$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$c,  ;!!'' ,;
,;;;!!!!!!!!''``.,;;;;!'`'  z$$$$$$$$???"""""'.,,.`"?$$$$$$$$$$$  ``,;;!!!
;;..       --''```_..,;;!  J$$$$$$??,zcd$$$$$$$$$$$$$$$$$$$$$$$$h  ``'``'
```'''   ,;;''``.,.,;;,  ,$$$$$$F,z$$$$$$$$$$$$$$$$$$$c,`""?$$$$$h
!!!!;;;;,   --`!'''''''  $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$h.`"$$$$h .
`'''``.,;;;!;;;--;;   zF,$$$$$$$$$$?????$$$$$$$$$$$$$?????$$r ;?$$$ $.
!;.,..,.````.,;;;;  ,$P'J"$$$$$$P" .,c,,.J$$$$$$$$$"',cc,_`?h.`$$$$ $L
'``````'    .,..  ,$$". $ $$$$P",c$$$$$$$$$$$$$$$$',$$$$$$$$$$ $$$$ $$c,
!!!!!!!!!!!!!'''  J$',$ $.`$$P c$$$$$$$$$$$$$$$$$$,$$$$$$$$$$$ $$$$ $$$$C
   ``            J$ ,$P $$ ?$',$$$$???$$$$$$$$$$$$$$$??"""?$$$ <$$$ $$$$$
c           ;,  z$F,$$  `$$ $ ?$"      "$$$.?$$$ $$$P c??c, ?$.<$$',$$$$$F
$$h.  -!>   ('  $" $F ,F ?$ $ F ,="?$$c,`$$F $$"z$$',$' ,$$P $h.`$ ?$$$$$r
$$$$$hc,. ``'  J$ $P J$ . $$F L ",,J$$$F <$hc$$ "$L,`??????,J$$$.` z$$$$$
$$$$$$$$$$c,'' ?F,$',$F.: $$ c$c,,,,,c,,J$$$$$$$ ?$$$c,,,c$$$$$$F. $$$$$$
`"$$$$$$$$$$$c, $$',$$ :: $$$$$$$$F"',$$$$$$$$$$h ?$$$L;;$$$??$$$$ $$$$$$
   "?$$$$$$$$$$ $$$$$$ : .`F"$$$$$$$$$$$$""""?"""h $$$$$$$"$,J$$$$ $$$$$'
      "?$$$$$$$ $$$$$$.`.` h `$$$$$$$$$$$cccc$$c,zJ$$$$$P' $$$$$P',$$$$P
$.       `""?$$ $$$$$$$  ` "$c "?$$$$$$$$$$$$??$$$$$$$$" ,J$$$P",J$$$$P
..           `" ?$$$$$$h    ?$$c.`?$$$$$$$$$' . <$$$$$' ,$$$"  ,$$$$$"
!!>. .          `$$$$$$$h  . "$$$c,"$$$$$$$' `' `$$$P  ,$$$' ,c$$$$$'   ;!
```<!!!>         `$$$$$$$c     "$$$c`?$$$$$  : : $$$  ,$$P' z$$$$$$'   ;!!
$hc ```'  ;       `$$$$$$$.      ?$$c ?$$$$ .: : $$$  $$F ,J$$$$$$'   ;!!
.,..      '        `$$$$$$$       "$$h`$$$$ .' ' $$$ ,$$ ,J$$$$$$'    !!!
????P               `$$$$$$L       $$$ $$$F :.: J$$P J$F J$$$$$P     ;!!
-=<                  ?$$."$$       `$$ ?$$' `' z$$$F $P  $$$$$$'     !!'
cc                   `$$$c`?        ?$.`$$hc, cd$$F ,$'  $$$$$$     ;!!
                      $$$$c         `$$c$$$$$$$$$",c$'   $$$$$$     `!!
                      $$$$$          `?$$$$$$$$$$$$P'    $$$$$$> ..
                      $$$$$            `"?$$$$$$$P"      $$$$$$L $$c,
          !!         <$$$$$            zc,`"""',         <$$$$$$.`$$$$cc,
          !!         J$$$$P            `$$$$$$$' !'       $$$$$$L `$$$$$$h
         ;,          $$$$$L          `! J$$$$$',!!        $$$$$$$  `$$$$$$
          '         <$$$$$.           ! $$$$$$ !!         ?$$$$$$   `$$$$$
                   ,$$$$$$$c          `,`???? ;'         c,?$$$$'    `?$$$
                   $$$$$$$??           `!;;;;!     .     `h."?$P      `$$$
                  ,$$$$$$$h.            `'''      `'      `$$$P        `?$
                   $$$$$$$$h                      `!'      `"'           `
                  `$$$$$$$$F          !;     !    ;,
                   `$$$$$$$'         `!!>         `!
c,        ;,        `?$$$$P           !!>             .
$F        !!>         `""'            `!!            ;!>    <-
                     The General Strategy of Shellphish

The Mechanical Phish was only about three months old when the final event
of the Cyber Grand Challenge took place. Like any newborn, its strategic
thought processes were not well developed and, unfortunately, the
sleep-deprived hackers of Shellphish were haphazard teachers at best. In
this section, we describe what amounted to our game strategy for the
Mechanical Phish and how the rules of the Cyber Grand Challenge, combined
with this strategy, impacted the final result.


* Development Strategy


The Shellphish CGC team was comprised completely of researchers at the UC
Santa Barbara computer security lab. Unfortunately, research labs are
extremely disorganized environments. Also unfortunately, as most of us were
graduate students, and graduate students need to do research to survive
(and eventually graduate), we were fairly limited in the amount of time
that we could devote to the CGC. For example, for the CGC Qualification
Event, we built our CRS in two and a half weeks. For the final event, we
were able to devote a bit more time: on average, each member of the team
(the size of which gradually increased from 10 to 13 over the course of the
competition) probably spent just under three months on this insanity.

One thing that bit us is that we put off true integration of all of the
components until the last minute. This led to many last-minute performance
issues, some of which we did not sort out before the CFE.


* Exploitation Strategy

Our exploitation strategy was simple: we attack as soon and as frequently
as possible. The only reason that we found to hold back was to avoid
letting a victim team steal an exploit. However, there was not enough
information in the consensus evaluation to determine whether a team did or
did not have an exploit for a given service (and attempting to recover this
fact from the network traffic was unreliable), so we decided on a "Total
War" approach.


* Patching Strategy

For every not-failing RB, we submitted the patch considered as the most
likely to have a better performance score. Specifically, given the way in
which RBs were created, we ranked RBs according to the following list:
Optimized Reassembled RB, Reassembled RB, Detouring RB. This choice was
motivated by the fact that detouring is slow (as it causes cache flushes
due to its propensity to jumping to many code locations), whereas the
generated optimized RBs are fast. Of course, we could not always rely on
the reassembler (and optimizer) to produce a patch, as these backends had
some failure cases.

For every patch submitted, the corresponding CS is marked down for a round.
Because this can be (and, in the end, was) debilitating to our score, we
evaluated many strategies with regards to patching during the months before
the CFE. We identified four potential strategies:

- Never patch: The simplest strategy was to never patch. This has the
 advantage of nullifying the chances of functionality breakages and
 avoiding the downtime associated with patching.

- Patch when exploited: The optimal strategy would be to patch as soon as
 we detect that a CS was being exploited. Unfortunately, detecting when a
 CS is exploited is very difficult. For example, while the consensus
 evaluation does provide signals that the binaries cause, these signals do
 not necessarily correlate to exploitation. Furthermore, replaying
 incoming traffic to detect exploitation is non-trivial due to complex
 behaviors on the part of the challenge binaries.

- Patch after attacking: An alternative strategy is to assume that an
 opponent can quickly steal our exploits, and submit a patch immediately
 after such exploits are fired. In our latter analysis, we determined that
 this would have been the optimal strategy, granting us first place.

- Always patch: If working under the assumption that the majority of
 challenge sets are exploited, it makes sense to always patch.

Most teams in the Cyber Grand Challenge took this decision very seriously.
Of course, being the rag-tag group of hackers that we are, we did some
fast-and-loose calculations and made a result based on data that turned out
to be incorrect. Specifically, we assumed that a similar fraction of the
challenges would be exploited as the fraction of challenges crashed during
the CQE (about 70%). At the time, this matched up with the percentage of
sample CGC binaries, provided by DARPA during sparring partner rounds, that
we were exploiting. Running the numbers under this assumption led us to
adopt the "always patch" approach:

1. At the second round of a challenge set's existence, we would check if we
  had an exploit ready. If not, we would patch immediately, with the best
  available patch (out of the three discussed above). Otherwise, we would
  delay for a round so that our exploit had a chance to be run against
  other teams.

2. Once a patch was deployed, we would monitor performance feedback.

3. If feedback slipped below a set threshold, we would revert to the
  original binary and never patch again.

In this way, we would patch *once* for every binary. As we discuss later,
this turned out to be one of the worst strategies that we could have taken.



--[ 007 - Fruits of our Labors

In early August, our creation had to fight for its life, on stage, in front
of thousands of people. The Mechanical Phish fought well and won third
place, netting us $750,000 dollars and cementing our unexpected place as
the richest CTF team in the world (with a combined winnings of 1.5 million
dollars, Shellphish is the first millionaire CTF team in history!).

This is really cool, but it isn't the whole story. The CGC generated
enormous amounts of data, and to truly understand what happened in the
final event, we need to delve into it. In this section, we'll talk
specifically regarding what happened, who achieved what, and how the CGC
Final Event played out.

For reference throughout this section, the final scores of the CGC Final
Event were:

            +--------------+------------------+---------+
            | Team         | CRS Name         | Points  |
            +--------------+------------------+---------+
            | ForAllSecure | Mayhem           | 270,042 |
            | TECHx        | Xandra           | 262,036 |
            | Shellphish   | Mechanical Phish | 254,452 |
            | DeepRed      | Rubeus           | 251,759 |
            | CodeJitsu    | Galactica        | 247,534 |
            | CSDS         | Jima             | 246,437 |
            | Disekt       | Crspy            | 236,248 |
            +--------------+------------------+---------+

The attentive reader will notice that the score of the Mechanical Phish is
the only one that is a palindrome.


--[ 007.001 - Bugs

The CGC was the first time that autonomous systems faced each other in a
no-humans-allowed competition. As such, all of the Cyber Reasoning Systems
likely faced some amount of bugs during the CFE. The most visible was
Mayhem's, which resulted in the system being off-line for most of the
second half of the game (although, as we discuss later in this section,
that might not have hurt the system as much as one would think). Our
system was no different. In looking through the results, we identified a
number of bugs that the Mechanical Phish ran into during the CFE:

* Multi-CB pipeline assertions

We used fuzzing to identify crashes and POV Fuzzing to fuzz those crashes
into POVs for challenge sets comprising of multiple binaries.
Unfortunately, an accidental assert statement placed in the POV Fuzzing
code caused it to opt out of any tasks involving multi-CB challenge sets,
disabling our multi-CB exploitation capability.

* Network traffic synchronization

Due to a bug, the component that scheduled tasks to synchronize and analyze
network traffic was set to download *all* recorded network traffic every
minute. The volume of this traffic quickly caused it to exceed scheduling
timeouts, and Mechanical Phish only analyzed network traffic for the first
15 rounds of the game.

* RB submission race condition

Due to a race condition between the component that determined what patches
to submit and the component that actually submitted them, we had several
instances where we submitted different patched binaries across different
rounds, causing multiple rounds of lost uptime.

* Scheduling issues

Throughout the CFE, Mechanical Phish identified exploitable crashes in over
40 binaries.  However, only 15 exploits were generated.  Part, but not all,
of this was due to the multi-CB pipeline assertions.  It seems that the
rest was due to scheduling issues that we have not yet been able to
identify.

* Slow task spawning

Our configuration of Kubernetes was unable to spawn tasks quickly enough to
keep up with the job queue.  Luckily, we identified this bug a few days
before the CFE and put in some workarounds, though we did not have time to
fix the root cause.  This bug caused us to under-utilize our
infrastructure.


--[ 007.002 - Pwning Kings

Over the course of the CGC Final Event, the Mechanical Phish pwned the most
challenges out of the competitors and stole the most flags. This was
incredible to see, and is an achievement that we are extremely proud of.
Furthermore, the Mechanical Phish stole the most flags even when taking
into account only the first 49 rounds, to allow for the fact that Mayhem
submitted its last flag on round 49.

We've collected the results in a helpful chart, with the teams sorted by
the total amount of flags that the teams captured throughout the game.

+--------------+-------------------------------+--------------------------+
| Team         | Flags Captured (first 49/all) | CSes Pwned (first 49/all)|
+--------------+-------------------------------+--------------------------+
| Shellphish   |           206 / 402           |          6 / 15          |
| CodeJitsu    |            59 / 392           |          3 / 9           |
| DeepRed      |           154 / 265           |          3 / 6           |
| TECHx        |            66 / 214           |          2 / 4           |
| Disekt       |           101 / 210           |          5 / 6           |
| ForAllSecure |           185 / 187           |         10 / 11          |
| CSDS         |            20 / 22            |          1 / 2           |
+--------------+-------------------------------+--------------------------+

Interestingly, Mayhem exploited an enormous amount of binaries before it
went down, but the Mechanical Phish still achieved a higher exploitation
score in the rounds that Mayhem was alive. One possibility is that the
exploits launched by the Mechanical Phish were more reliable than those of
Mayhem. However, its raw exploitation power should not be underestimated:
within 49 rounds, before going off the grid, Mayhem managed to exploit 10
binaries. While the Mechanical Phish surpassed it over the entire game,
this is still quite impressive.


--[ 007.003 - Patching Kings

To understand how effective our patches were, we calculated the number of
flags lost (and the number of CSes on which flags were lost) throughout the
game, both for the first 49 rounds (in which Mayhem was online) and for the
entire game. As expected, because the Mechanical Phish patched every
binary, we found that it was the least-exploited CRS. Specifically, it only
leaked flags on 12 challenge sets. The runner-up in this sense (the
second-place team, TECHx), leaked flags on 14 binaries.

Interestingly, TECHx beat us on the total number of flags leaked. This
makes sense -- they likely had some analysis to identify *when* they were
being exploited, and patch only then. And, likely, their patches were more
effective than our own, leading to a lower number of total flags leaked!

The results, sorted by the number of compromised challenges, are:

+--------------+-------------------------------+--------------------------+
| Team         | Defended CS-Rounds (49/all)   | CSes Compromised (49/*)  |
+--------------+-------------------------------+--------------------------+
| Shellphish   |           29 / 68             |          7 / 12          |
| TECHx        |           27 / 61             |          7 / 14          |
| DeepRed      |           32 / 87             |          6 / 15          |
| ForAllSecure |           54 / 160            |          7 / 16          |
| CodeJitsu    |           61 / 104            |          9 / 16          |
| Disekt       |           66 / 127            |          9 / 17          |
| CSDS         |          108 / 189            |          9 / 18          |
+--------------+-------------------------------+--------------------------+


--[ 007.004 - Patching Effectiveness

Before the CFE, we tested our patches against the dataset of all CQE
binaries released until that point, compiled with many different
compilation flags. On this dataset, our chance of breaking a binary, or
lowering performance to below 85% (the guesstimated threshold at which we
would pull the binary back) was under 2%, and we decided to abandon patch
performance/functionality testing. On the actual CFE dataset, we fared
worse.

The CFE had 82 challenge sets. For these 82 challenge sets, we successfully
generated patches for 78. Of these 78, we had to pull back 10 because the
patch broke the binary and 7 because the patch lowered the performance of
the binary below acceptable levels. This was considerably higher than
expected. Furthermore, due to a race condition between the patch submission
logic and the component that retrieves the game state, we did end up with
situations where we would submit *multiple* patches, thinking that the
round had not ended whereas, in reality, it had. In total, we made 107 RCB
submissions throughout the game. This was the second-highest amount, with
only CodeJitsu submitting more (108).

Because very few challenges were exploited during the CFE, this was
unequivocally the wrong choice. In total, we lost around 17000 points
during the "downtime" rounds after the patch submissions alone.


--[ 007.005 - Alternate History Case Studies

Hindsight is 20/20. Even though we know, now, that we made the wrong choice
regarding our patching strategy, it's still interesting to see what "could
have been". In this section, we do that. To better understand the impact of
our strategy decisions, we compute scores for several simulated CGC rounds
where the Mechanical Phish undertook different strategies, and see what
would have happened.

It's very important to point out that this is all fantasy. *Every* team can
look back and consider things that they might have done differently. The
most obvious one is Mayhem: had they avoided crashing, they might have
absolutely dominated the competition, rather than relaxedly coasting to
victory. However, every other team has other "what if" moments. We explore
ours here purely out of curiosity.

* Mechanical Phish that never patched

To calculate our score in the absence of patching, we recalculated CFE
scores, assuming that, any time an exploit would be launched on a CS
against *any* team, the exploit would be run against us during that round
and all subsequent rounds of that CS being in play. With this calculation,
our score would be 267,065, which is 12,613 points higher than the patch
strategy that we did choose and would put us in second place by a margin of
over 5,000 points.

The prize for second place was $1,000,000. Patching at all cost us
$250,000!

* Mechanical Phish that patched after attacking

Similar to the previous strategy, we calculated our score with a patch
strategy that would delay patches until *after* we launched exploits on the
corresponding CS. For the patches that would have been submitted, we used
the same feedback that we received during the CFE itself. With this
calculation, our score would be 271,506, which is 17,054 points higher than
the patch strategy that we chose and would have put us in first place by a
margin of over 1,500 points.

The prize for first place was $2,000,000. Patching stupidly cost us
$1,250,000 and quite a bit of glory!

* Mechanical Phish that didn't do crap

We were curious: did we really have to push so hard and trade so much
sanity away over the months leading up to the CGC? How would a team that
did *nothing* do? That is, if a team connected and then ceased to play,
would they fare better or worse than the other players?  We ran a similar
analysis to the "Never patch" strategy previously (i.e., we counted a CS as
exploited for all rounds after its first exploitation against any teams),
but this time removed any POV-provided points. In the CFE, this "Team NOP"
would have scored 255,678 points, barely *beating* Shellphish and placing
3rd in the CGC.

To be fair, this score calculation does not take into account the fact that
teams might have withheld exploits because all opponents were patched
against them. However, ForAllSecure patched only 10 binaries, so it does
not seem likely that many exploits were held back due to the presence of
patches.

One way of looking at this is that we could have simply enjoyed life for a
year, shown up to the CGC, and walked away with $750,000. Another way of
looking at this is that, despite us following the worst possible strategy
in regards to patching, the technical aspects of our CRS were good enough
to compensate and keep us in the top three positions!


--[ 007.006 - Scoring Difficulties

Similarly to this being the first time that autonomous systems
compete against each other in a no-humans-allowed match, this was also the
first time that such a match was *hosted*. The organizing team was up
against an astonishing amount of challenges, from hardware to software to
politics, and they pulled off an amazing event.

However, as in any complex event, some issues are bound to arise.  In this
case, the problem was that measuring program performance is hard. We found
this out while creating our CRS, and DARPA experienced this difficulty
during the final event. Specifically, we noticed two anomalies in the
scoring data: slight disparities in the initial scoring of challenge sets,
and performance "cross-talk" between services.

* Initial CS Scoring

Patches can only be fielded on round 3 (after being submitted on round 2)
of a binary being deployed. However we noticed that our availability scores
were lower than our opponents, even on the *first* round of a challenge,
when they could not yet be patched. In principle, these should all be the
same, as a team has *no* way to influence this performance score.  We
calculated the average of the first-round CS availability scores, presented
in the table below. The scores vary. The difference between the
"luckiest" team, regarding their first-round CS score, and the "unluckiest"
team was 1.6 percentage points. Unfortunately, Shellphish was that
unluckiest team.

Since the availability score was used as a multiplier for a team's total
score, if the "luckiest" and "unluckiest" had their "luck" swapped, this
would compensate for a total score difference of 3.2%. That is a bigger
ratio than the difference between second and third place (2.9%), third and
fourth place (1.1%), fourth and fifth place (1.7%), and fifth and sixth
place (0.4%). The winner (Mayhem) could not have been unseated by these
perturbations, but the rest of the playing field could have looked rather
different.

+--------------+----------------------------------+
| Team         | Average First Round Availability |
+--------------+----------------------------------+
| CSDS         |              0.9985              |
| ForAllSecure |              0.9978              |
| Disekt       |              0.9975              |
| TECHx        |              0.9973              |
| CodeJitsu    |              0.9971              |
| DeepRed      |              0.9917              |
| Shellphish   |              0.9824              |
+--------------+----------------------------------+

* Scoring Cross-talk

We also noticed that performance measurements of one challenge seem to
influence others. Specifically, when we patched the binary NRFIN_00066 on
round 39, we saw the performance of *all* of our other, previously-patched,
binaries drop drastically for rounds 40 and 41. This caused us to pull back
patches for *all* of our patched binaries, suffering the resulting downtime
and decrease in security.

Anecdotally, we spoke to two other teams, DeepRed and CodeJitsu, that were
affected by such scoring cross-talk issues.



--[ 008 - Warez

We strongly believe in contributing back to the community. Shortly after
qualifying for the Cyber Grand Challenge, we open-sourced our binary
analysis engine, angr. Likewise, after the CGC final event, we have
released our entire Cyber Reasoning System. The Mechanical Phish is open
source, and we hope that others will learn from it and improve it with us.

Of course, the fact that we directly benefit from open-source software
makes it quite easy for us to support open-source software. Specifically,
the Mechanical Phish would not exist without amazing work done by a large
number of developers throughout the years. We would like to acknowledge the
non-obvious ones (i.e., of course we are all thankful for Linux and vim)
here:

* AFL (lcamtuf.coredump.cx/afl) - AFL was used as the fuzzer of every
  single competitor in the Cyber Grand Challenge, including us. We all owe
  lcamtuf a great debt.
* PyPy (pypy.org) - PyPy JITed our crappy Python code, often increasing
  runtime by a factor of *5*.
* VEX (valgrind.org) - VEX, Valgrind's Intermediate Representation of
  binary code, provided an excellent base on which to build angr, our
  binary analysis engine.
* Z3 (github.com/Z3Prover/z3) - angr uses Z3 as its underlying constraint
  solver, allowing us to synthesize inputs to drive execution down specific
  paths.
* Boolector (fmv.jku.at/boolector) - The POVs produced by the Mechanical
  Phish required complex reasoning about the relation between input and
  output data. To reduce implementation effort, we wanted to use a
  constraint solver to handle these relationships. Because Z3 is too huge
  and complicated to include in a POV, we ported Boolector to the CGC
  platform and included it in every POV the Mechanical Phish threw.
* QEMU (qemu.org) - The heavy analyses that angr carries out makes it
  considerably slower than qemu, so we used qemu when we needed
  lightweight, but fast analyses (such as dynamic tracing).
* Unicorn Engine (www.unicorn-engine.org) - angr uses Unicorn Engine to
  speed up its heavyweight analyses. Without Unicorn Engine, the number of
  exploits that the Mechanical Phish found would have undoubtedly been
  lower.
* Capstone Engine (www.capstone-engine.org) - We used Capstone Engine to
  augment VEX's analysis of x86, in cases when VEX did not provide enough
  details. This improved angr's CFG recovery, making our patching more
  reliable.
* Docker (docker.io) - The individual pieces of our infrastructure ran in
  Docker containers, making the components of the Mechanical Phish
  well-compartmentalized and easily upgradeable.
* Kubernetes (kubernetes.io) - The distribution of docker containers across
  our cluster, and the load-balancing and failover of resources, was
  handled by kubernetes. In our final setup, the Mechanical Phish was so
  resilient that it could probably continue to function in some form even
  if the rack was hit with a shotgun blast.
* Peewee (https://github.com/coleifer/peewee) - After an initial false
  start with a handcrafted HTTP API, we used Peewee as an ORM to our
  database.
* PostgreSQL (www.postgresql.org) - All of the data that the Mechanical
  Phish dealt with, from the binaries to the testcases to the metadata
  about crashes and exploits, was stored in a ridiculously-tuned and
  absurdly replicated Postgres database, ensuring speed and resilience.

As for the Mechanical Phish, this release is pretty huge, involving many
components. This section serves as a place to collect them all for your
reference. We split them into several categories:

--[ 008.001 - The angr Binary Analysis System

For completeness, we include the repositories of the angr project, which we
open sourced after the CQE. However, we released several additional
repositories after the CFE, so we list the whole project here.

* Claripy

Claripy is our data-model abstraction layer, allowing us to reason about
data symbolically, concretely, or in exotic domains such as VSA. It is
available at https://github.com/angr/claripy.

* CLE.

CLE is our binary loader, with support for many different binary formats.
It is available at https://github.com/angr/cle.

* PyVEX.

PyVEX provides a Python interface to the VEX intermediate representation,
allowing angr to support multiple architectures. It is available at
https://github.com/angr/pyvex.

* SimuVEX.

SimuVEX is our state model, allowing us to handle requirements of different
analyses. It is available at https://github.com/angr/simuvex.

* angr.

The full-program analysis layer, along with the user-facing API, lives in
the angr repository. It is available at https://github.com/angr/angr.

* Tracer.

This is a collection of code to assist with concolic tracing in angr. It is
available at https://github.com/angr/tracer.

* Fidget.

During the CQE, we used a patching method, called Fidget, that resized and
rearranged stack frames to prevent vulnerabilities. It is available at
https://github.com/angr/fidget.

* Function identifier.

We implemented testcase-based function identification, available at
https://github.com/angr/identifier.

* angrop.

Our ROP compiler, allowing us to exploit complex vulnerabilities, is
available at https://github.com/salls/angrop.


--[ 008.002 - Standalone Exploitation and Patching Tools

Some of the software developed for the CRS can be used outside of the
context of autonomous security competitions. As such, we have collected it
together in a separate place.

* Fuzzer.

We created a programmatic Python interface to AFL to allow us to use AFL as
a module, within or outside of the CRS. It is available at
https://github.com/shellphish/fuzzer.

* Driller.

Our symbolic-assisted fuzzer, which we used as the crash discovery
component of the CRS, is available at
https://github.com/shellphish/driller.

* Rex.

The automatic exploitation system of the CRS (and usable as a standalone
tool) is available at https://github.com/shellphish/rex.

* Patcherex.

Our automatic patching engine, which can also be used standalone, is
available at https://github.com/shellphish/patcherex.


--[ 008.003 - The Mechanical Phish Itself

We developed enormous amounts of code to create one of the world's first
autonomous security analysis systems. We gathered the code that is specific
to the Mechanical Phish under the mechaphish github namespace.


* Meister.

The core scheduling component for analysis tasks is at
https://github.com/mechaphish/meister.

* Ambassador.

The component that interacted with the CGC TI infrastructure is at
https://github.com/mechaphish/ambassador.

* Scriba.

The component that makes decisions on which POVs and RBs to submit is
available at https://github.com/mechaphish/scriba.

* Docker workers.

Most tasks were run inside docker containers. The glue code that launched
these tasks available at https://github.com/mechaphish/worker.

* VM workers.

Some tasks, such as final POV testing, was done in a virtual machine
running DECREE. The scaffolding to do this is available at
https://github.com/mechaphish/vm-workers.

* Farnsworth.

We used a central database as a data store, and used an ORM to access it.
The ORM models are available at https://github.com/mechaphish/farnsworth.

* POVSim.

We ran our POVs in a simulator before testing them on the CGC VM (as the
latter is a more expensive process). The simulator is available at
https://github.com/mechaphish/povsim.

* CGRex.

Used only during the CQE, we developed a targeted patching approach that
prevents binaries from crashing. It is available at
https://github.com/mechaphish/cgrex.

* Compilerex.

To aid in the compilation of CGC POVs, we collected a set of templates and
scripts, available at https://github.com/mechaphish/compilerex.

* Boolector.

We ported the Boolector SMT solver to the CGC platform so that we could
include it in our POVs. It is available at
https://github.com/mechaphish/cgc-boolector.

* Setup.

Our scripts for deploying the CRS are at
https://github.com/mechaphish/setup.

* Network dude.

The CRS component that retrieves network traffic from the TI server is at
https://github.com/mechaphish/network_dude.

* Patch performance tester.

Though it was not ultimately used in the CFE, because performance testing
is a very hard problem, our performance tester is at
https://github.com/mechaphish/patch_performance.

* Virtual competition.

We extended the provided mock API of the central server to be able to more
thoroughly exercise Mechanical Phish. Our extensions are available at
https://github.com/mechaphish/virtual-competitions.

* Colorguard.

Our Type-2 exploit approach, which uses an embedded constraint solver to
recover flag data, is available at
https://github.com/mechaphish/colorguard.

* MultiAFL.

We created a port of AFL that supports analyzing multi-CB challenge sets.
It is available at https://github.com/mechaphish/multiafl.

* Simulator.

To help plan our strategy, we wrote a simulation of the CGC. It is
available at https://github.com/mechaphish/simulator.

* POV Fuzzing.

In addition to Rex, we used a backup strategy of "POV Fuzzing", where a
crashing input would be fuzzed to determine relationships that could be
used to create a POV. These fuzzers are available at
https://github.com/mechaphish/pov_fuzzing.

* QEMU CGC port.

We ported QEMU to work on DECREE binaries. This port is available at
https://github.com/mechaphish/qemu-cgc.



--[ 009 - Looking Forward

Shellphish is a dynamic team, and we are always looking for the next
challenge. What is next? Even we might not know, but we can speculate in
this section!


* Limitations of the Mechanical Phish

The Mechanical Phish is a glorified research prototype, and significant
engineering work is needed to bring it to a point where it is usable in the
real world. Mostly, this takes the form of implementing the environment
model of operating systems other than DECREE. For example, the Mechanical
Phish can currently analyze, exploit, and patch Linux binaries, but only if
they stick to a very limited number of system calls.

We open-sourced the Mechanical Phish in the hopes that work like this can
live on after the CGC, and it is our sincere hope that the CRS continues to
evolve.


* Cyber Grand Challenge 2?

As soon as the Cyber Grand Challenge ended, there were discussions about
whether or not there would be a CGC2. Generally, DARPA tries to push
fundamental advances: they did the self-driving Grand Challenge more than
once years, but this seems to be because no teams won it the first time.
The fact that they have not done a self-driving Grand Challenge since
implies that DARPA is not in the business of running these huge
competitions just for the heck of it: they are trying to push research
forward.

In that sense, it would surprise us if there was a CGC2, on DECREE OS, with
the same format as it exists now. For such a game to happen, the community
would probably have to organize it themselves. With the reduced barrier to
entry (in the form of an open-sourced Mechanical Phish), such a competition
could be pretty interesting. Maybe after some more post-CGC recovery, we'll
look into it!

Of course, we can also sit back and see what ground-breaking concept DARPA
comes up with for another Grand Challenge. Maybe there'll be hacking in
that one as well.


* Shellphish Projects

The Mechanical Phish and angr are not Shellphish's only endeavors. We are
also very active in CTFs, and one thing to come out of this is the
development of various resources to help newbies to CTF. For example, we
have put together a "toolset" bundle to help get people started in security
with common security tools (github.com/zardus/ctf-tools), and, in the
middle of the CGC insanity, ran a series of hack meetings in the university
to teach people, by example, how to perform heap meta-data attacks
(github.com/shellphish/how2heap). We're continuing down that road, in fact.
Monitor our github for our next big thing!
`


--[ 010 - References

[Driller16] Driller: Augmenting Fuzzing Through Selective Symbolic
Execution
Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang,
Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, Giovanni Vigna
Proceedings of the Network and Distributed System Security Symposium (NDSS)
San Diego, CA February 2016

[ArtOfWar16] (State of) The Art of War: Offensive Techniques in Binary
Analysis
Yan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens, Mario
Polino, Andrew Dutcher, John Grosen, Siji Feng, Christophe Hauser,
Christopher Kruegel, Giovanni Vigna
Proceedings of the IEEE Symposium on Security and Privacy San Jose, CA May
2016

[Ramblr17] Ramblr: Making Reassembly Great Again
Ruoyu Wang, Yan Shoshitaishvili, Antonio Bianchi, Aravind Machiry, John
Grosen, Paul Grosen, Christopher Kruegel, Giovanni Vigna
Proceedings of the Network and Distributed System Security Symposium (NDSS)
San Diego, CA February 2017

[angr] http://angr.io

[Inversion] https://en.wikipedia.org/wiki/Sleep_inversion

[CGCFAQ] https://cgc.darpa.mil/CGC_FAQ.pdf


|=[ EOF ]=---------------------------------------------------------------=|