Dynamically writing polls
Challenge binary interactivity verification within the context of the DARPA Cyber Grand Challenge is implemented via specialized unit tests known as "service polls". Service polls are intended to validate the performance and functionality of challenge binaries in order to test the efficacy and impact of reformulation performed by competitors. Similar in ideals to unit tests, service polls should be written to validate the interactivity and complex state machines implemented by CBs.
Due to the requirements for CB authors to deliver a large number of CB validations that are both deterministic and unique, a service poll generator has been provided that will be used to assist in developing these polls.
Developing services polls using the generator is performed through the use of a weighted directed graph, and an associated python module that implements the state machine that is used to generate the polls.
The Directed Graph specifies the connection between each individual components within the state machine, allowing a CB author to define the polls as small individual components, and explore the combinatorial permutations of between the different components for CB validation.
The directed graph defines individual nodes, which relate to a method in the provided python class, and edges, which define which nodes could be called upon completion of the execution of a given node.
These components are defined in YAML, at the top level as a dictionary,
nodes entry is composed of a list of dictionaries, each defining an
individual node. Each dictionary must contain the key
name, which is a
string that defines the name of the given node. The value of the
corresponds to the name of the method within the provided python module that
should be executed upon accessing that node during the graph traversal.
Within this dictionary, two additional entries are supported:
continue, if provided, are specified as
floats between 0.0 and 1.0.
continueallows the developer to specify the likelihood that the state machine should continue processing upon execution of the node.
chanceallows the developer to specify the likelihood that the state machine should execute the node, or continue traversal of the graph without executing the underlying functionality of the node.
Node names must be unique. If the node name
start is provided, then
traversal will always begin at this node, otherwise, the traversal will start
at a random node in the graph.
edges entry is composed of a list of dictionaries, each defining an edge between two nodes. Each dictionary can have up to two entries, with the first defining the start and end nodes for a given edge. The key and value both refer to a node defined in the
nodes entry. Within this dictionary, two additional entries are supported:
weight, if provided, is specified as a float between 0.0 and 1.0.
after, if provided, is specified as a float between 0.0 and 1.0.
weightallows the developer to specify the likelihood of traversal of a given edge when a node has multiple edges leaving the node within the graph.
afterallows the developer to specify that a path may only be included in the traversal allows the developer enable code paths be enabled after a specified percentage of polls have been generated.
The State Machine is a python class, which defines the implementations of methods that perform the interactions with a service for a given state. The underlying implementation is a subclass of the generator.Actions python class provided as part of the poll-generation package.
This class provides a set of methods that perform specific functions that are
reliant for CB interactions performed via the XML DTD used by
These methods are:
read: creates a read interaction
write: creates a write interaction
xml: create an XML for all of the existing interactions
chance: simple to use wrapper to get a
Falsevalue, specifying the likelihood that
Truewill be taken via a float between 0.0 and 1.0.
reset: resets the internal state of the machine, which is called per iteration of the graph traversal.
To create a state machine for use within the
generate-polls, provide methods
for each node in the directed graph described above. Each method should call
self.write as needed, which will implement read and write
interactions to the service.
There is a dictionary
state, that is provided by the parent class that can be
used for storing arbitrary intermediary values during execution of a given
iteration but is reset between each iteration. The
state dictionary is
reinitialized by the above
There is also a per-poll
magic_page string will be used in the challenge binary, allowing for perfect knowledge of the magic page as discussed in
Sample Implementation Walk Through
A sample implementation of a poll generator, ftplite, is provided in the /usr/share/poll-generator/examples/. This generator provides a state machine interaction to an FTP like protocol.
The 9 unique states in the machine, defined as the following:
Each of these states have an entry in the graph as well as a method in the python implementation of the state machine.
Looking at the python implementation, there are a few items of note. The methods
after_login are empty methods. These methods are used as a common
point for the directed graph to connect into.
start method is provided such that each iteration of walking the state
machine starts at the same location.
after_login method provides a common location in the graph that can such
that each of the methods intended to be run in an arbitrary combinations once
logins have occurred do not need to link to all of the rest of the methods.
state dictionary, the key
login is used to track if the
state successfully completed. This shows the ability to store and access
arbitrary information between states within the graph.
Sample Implementation Walk Through 2
This is a step-by-step walkthrough for the overly simple
CADET_00001 Palindrome service. The service is comprised of a banner on the initial connect, a banner requesting the user enter a possible palindrome, the user entering a palindrome, and the service returning back a response. We will build the state machine and the graph for this simple service.
Starting in the CADET_00001 directory edit poller/for-release/machine.py:
Python module dependancies
Service poll generators are required to import the Actions module. Any others are up to the author. In our example we also use the random and string modules.
from generator.actions import Actions import random import string
Service poll generation class
The service poll generator expects a class derived from the CGC Actions class. This class will define each individual state in a service poller state machine. This class should also contain an empty start member which serves as the entry to the state machine.
class Palindrome(Actions): def start(self): pass
The palindrome service always begins with a "Welcome to Palindrome Finder" banner with an extra carriage return before it. Our state machine needs confirm the presence of this banner.
def banner(self): # Confirm the initial empty line self.read(delim='\n', expect='\n') # Confirm the actual banner self.read(delim='\n', expect='Welcome to Palindrome Finder\n')
We've created our first node in the state machine, now we need to connect it in the graph. The state machine graph is constructed in the state-graph.yaml file. It is composed of two sections. 1. Node definitions 2. Node connections
The format of the file looks like
--- nodes: <add nodes here> edges: <add edges here>
Initial node definitions
We created two nodes,
banner, which must be defined in the state tree:
- name: start - name: banner
We also need to define the edge for the state machine to traverse from the fictional
start node into the banner:
- start: banner
We have a very rudimentary service poller generator that this point which can be tested. Generate one service poll via:
$ generate-polls --count 1 poller/for-release/machine.py poller/for-release/state-graph.yaml poller/for-release
- Please note that the above generation example will fail with more complex graphs since a single generation won't hit all of the nodes. The count must be expanded for these more complex graphs
A single service poll was created in
This service poll can be manually inspected or tested against the challenge binary with:
$ cb-test --cb CADET_00001 --directory bin --xml poller/for-release/gen_000000.xml
The expected output indicates that strings matched:
# service - poller/for-release/gen_000000.xml ok 1 - match: string ok 2 - match: string # passed: 2 # failed: 0 # total passed: 2 # total failed: 0
An alternative testing strategy involves spawning the CB in one window while connecting to it with the
cb-test utilility like so:
Window 1: sudo cb-server --insecure --once -p 12345 -d . bin/CADET_00001 Window 2: cb-replay --failure_ok --host 127.0.0.1 --port 12345 poller/for-release/gen_000000.xml
Handling palindrome requests
Following the banner, the service asks the user for possible palindromes. We must parse this request and test it with palindromes and non-palindromes.
def request(self): # Skip the empty line self.read(delim='\n', expect='\n') # Confirm the request self.read(length=37, expect='\tPlease enter a possible palindrome: ') def palindrome(self): halfword = self.random_string(random.randint(1, 16)) self.write(halfword + halfword[::-1] + "\n") self.read(delim='\n', expect='\t\tYes, that\'s a palindrome!\n\n') def not_palindrome(self): word = self.random_string(random.randint(2, 32)) while self.is_palindrome(word): word = self.random_string(random.randint(2, 32)) self.write(word + "\n") self.read(delim='\n', expect='\t\tNope, that\'s not a palindrome\n\n')
def is_palindrome(self, word): for i in range(0, len(word) / 2): if word[i] != word[-i - 1]: return False return True def random_string(self, size): chars = string.letters + string.digits return ''.join(random.choice(chars) for _ in range(size))
We created three nodes which must be defined in the state tree:
In the state tree:
- name: request continue: .9 - name: palindrome - name: not_palindrome
continue entry. There is a 90% chance that the poll generator will continue down the state graph on every service poll and a 10% chance that the service poll will stop.
We also need to define the edges for the state machine to traverse these nodes. First we link the previous
banner node into the
request node and then into the
- banner: request - request: palindrome weight: .2 - request: not_palindrome weight: .8
Note that each of the request edges contains a weight. 20% of the time the request will lead to a palindrome and 80% of the time it will lead to a non-palindrom.
Finally we must link both palindrome and not_palindrome back into the request since this is effectively a circular state graph.
- palindrome: request - not_palindrome: request
Evaluating the generated polls
The poll generated creates an
edges.png and a
nodes.png in the output directory. These should be manually inspected to confirm the desired graph traversals and nodes are reached.
A CRS is able to configure a submitted POV to be used more than once per round in case a POV is unreliable. The repeated use of a POV in a given round would allow for trivial identification of POVs via traffic analysis because polls are intended to never be reused through the course of the competition. The command line arguments
--duplicate provide the ability for the CB author to purposely reuse polls in a given round to mimic the potential of a POV being repeated used.
The command line argument
--duplicate specifies the number of polls that should appear multiple times in a round.
The command line argument
--repeat specifies the maximum number of times a poll that is repeated should appear in a round, which is variable between 1 and the specified amount.
The ability to repeat polls provides the CB author the ability to include repeated content, which reduces the ability of a CRS to identify POV traffic purely by content repetition.