ROSE  0.9.9.149
Binary analysis tutorial

Getting started guide for binary analysis.

Why binary analysis?

ROSE was originally designed as a source-to-source analysis and trasformation system, but it turns out that parsing and analyzing a binary specimen shares much of the same basic ideas:

Of course there are also many differences between source code and binary specimens, but ROSE is situated in the unique position of being able to process both. On the one hand, it can operate on a specimen for which no source code is available, and on the other it can perform analysis and transformations where both source and binary are available at once.

What binary analysis features are available?

ROSE can parse a variety of binary inputs. It can parse executable formats including Linux ELF executables, Microsoft Windows PE and DOS executables, and Motorola S-Records. It has disassemblers for ARM, Amd64 (x86-64), MIPS, Motorola 68k, PowerPC, and x86 families. It can read raw memory dumps if the user supplies mapping information, or it can obtain memory and register states from a running executable (Linux).

ROSE understands semantics for common subsets of Amd64, m68k, PowerPC, and x86 and can therefore reason about how execution of instructions affects a machine's state. It uses that information to drive recursive disassembly and discern where code and data are located. This reasoning can occur in various semantic domains: a domain that operates on concrete values like a real CPU, a domain that operates on symbolic values that can be fed into Satisfiability Modulo Theory (SMT) solvers, an interval domain that represents ranges of values, and many other more specialized domains and user-defined domains.

ROSE is able to construct control flow graphs and call graphs and has a number of pre-built analysis capabilities such as tainted flow analysis, edit distances, code statistics, memory maps, reasoning about register interactions, address usage maps, execution paths and their feasibility, generic inlining and interprocedural data-flow, no-op sequence detection, opaque predicate detection, algorithmic CFG rewriting, calling convention detection, function may-return analysis, address labeling passes, thunk detection and manipulating, switch statement analysis, interrupt vector processing, overlapping instructions, cross referencing, function stack delta analysis, register and memory usage analysis, magic numbers, static and dynamic string decoding, control flow dominance, pointer detection, DWARF parsing, library identification, etc.

Analysis results are available in a number of formats, depending on the analysis: through various APIs, decoration of the abstract syntax tree or control flow graph, commentary in assembly listings, databases, or to a certain extent, as a new translated binary specimen.

This document only attempts to describe a few of the easiest features to get you started.

Installing and confguring ROSE for binary analysis

The binary analysis features have a large number of software dependencies beyond what the source-to-source side of ROSE uses, but fortunately all of them are optional. If a software dependency is not available then the analysis that uses it is simply not available. In a few cases cases the analysis can use a different dependency or a slower or less accurate implementation. See Installing ROSE for instructions on how to install ROSE. ROSE must be configured with "binaries" being one of the "--enable-languages" values.

Hello, World!

Every system needs a basic "Hello, World!" example, so here's that example for binary analysis within the ROSE framework. It parses a specimen from a variety of formats (see its "--help" output), then disassembles the instructions optionally using instruction semantics to help drive the disassembly, then partitions the instructions into functional units, and finally displays an assembly listing.

#include <rose.h>

All programs start by including the main ROSE include file. This declares most things that are common to source and binary analysis.

#include <Partitioner2/Engine.h>
#include <AsmUnparser.h>

ROSE's binary components are declared in individual header files that can only be included after including "rose.h". This ordering is true in general for ROSE. The binary headers themselves can be included in any order since each header includes those other headers on which it depends. The binary analysis headers usually have the same names as the primary class they contain.

ROSE_INITIALIZE; // see Rose::initialize
std::string purpose = "disassembles a binary specimen";
std::string description =
"This tool disassembles the specified file and presents the results "
"as a pseudo assembly listing, a listing intended for human consumption "
"rather than assembling. This implementation serves as the \"Hello, "
"World!\" example for binary analysis, so let's keep it simple!";

The binary analysis uses a different command-line processor than most of the rest of ROSE because the command-line options for these tools don't typically interact with a compiler and therefore don't need to parse the host of compiler switches that the source tools need to recognize. This also frees the binary tool's command-line parser to be able to generate Unix man pages on the fly. For instance, if you invoke this tool with "--help" (or just "-h") you should see quite lengthy documentation about how to invoke the tool and what all its switches mean. A tool more advanced than "Hello, World!" can modify the command-line parser.

SgAsmBlock *gblock = engine.frontend(argc, argv, purpose, description);

ROSE divides disassembly into two phases. Within ROSE, a Disassembler is responsible for parsing the bytes of a single machine instruction and turning them into an abstract syntax tree, while the Partitioner2 namespace contains the machinery for driving disassembly. The partitioner partitions the specimen's memory image into parts that are either instructions or data (actually, "partitioner" is a bit of a misnomer since instructions and data can also overlap, although they seldom do in practice).

The Partitioner2 namespace contains many classes, but Engine is the highest abstraction and the one that most tools use. In this example, we are invoking the frontend, which is similar in nature to ROSE's global ::frontend in that it does everything necessary to make ROSE ready to do analysis: it parses, loads, disassembles, partitions, runs basic analysis, and checks consistency. In the end, it returns an abstract syntax tree (AST).

AST nodes in ROSE all begin with the letters "Sg" (from "Sage"). Those nodes that are specific to binary analysis begin with "SgAsm" (from "Sage assembly"). Within source code analysis, source files combine to form a single SgProject node, and the same is usually true with binary analysis also. For specimens that have a container, like Linux ELF and Windows PE files, the AST has two large subtrees: one subtree describes the containers (there may be more than one), and another subtree describes the instructions organized into interpretation subtrees (SgAsmInterpretation). Interpretations organize instructions into coherent sets, such as the PE32 and DOS subcomponents of a Windows PE file. However not all specimen formats have containers, in which case the AST is abbreviated and contains only the instructions rooted at a "global block" (SgAsmBlock).

unparser.unparse(std::cout, gblock);

Now that an abstract syntax tree has been created we can "unparse" it. Unparsing in a binary is slightly different than unparsing source code. Binary specimens are usually not transformed like source code, so the unparser for a binary generates a human-readable pseudo-assembly listing instead. We could have also called the global ::backend (same as source code) which would have produced a number of output files including a new executable, but backend only works on SgProject nodes which might not be present (see above).

Here's the entire "Hello, World!" program:

1 #include <rose.h>
4 
6 #include <Partitioner2/Engine.h>
7 #include <AsmUnparser.h>
9 
10 int
11 main(int argc, char *argv[]) {
13  ROSE_INITIALIZE; // see Rose::initialize
14  std::string purpose = "disassembles a binary specimen";
15  std::string description =
16  "This tool disassembles the specified file and presents the results "
17  "as a pseudo assembly listing, a listing intended for human consumption "
18  "rather than assembling. This implementation serves as the \"Hello, "
19  "World!\" example for binary analysis, so let's keep it simple!";
21 
24  SgAsmBlock *gblock = engine.frontend(argc, argv, purpose, description);
26 
29  unparser.unparse(std::cout, gblock);
31 }
Instruction basic block.
virtual size_t unparse(std::ostream &, SgNode *ast)
Unparse part of the AST.
Base class for engines driving the partitioner.
Definition: Engine.h:101
Unparses binary AST into text.
Definition: AsmUnparser.h:249
SgAsmBlock * frontend(int argc, char *argv[], const std::string &purpose, const std::string &description)
Most basic usage of the partitioner.

Compiling programs that use ROSE

To compile this program you'll want to use the same compiler, preprocessor switches, compiler switches, and loader switches as are used when compiling ROSE. This is important! Since C++ has no official, documented application binary interface, mixing libraries compiled with different compilers, compiler versions, compiler optimization levels, or even other seemingly benign compiler switches is not guaranteed to work. The easiest way to compile the above example is to change directories to $ROSE_BUILD/tutorial, where $ROSE_BUILD is the top of your build tree, and run make binaryHelloWorld. Similar commands will work for the other examples in this tutorial.

On the other hand, if you've already installed the ROSE library and blown away your build tree, or if you're writing your own programs that use ROSE, you won't be able to leverage ROSE's own build system to compile your program, and you probably have no idea what compiler command was used to compile ROSE. Fear not, ROSE installed a "rose-config" tool in its "bin" directory that has all this info (at least if you configured and built ROSE using GNU auto-tools; CMake users are out of luck for the time being). Using it is a three step process:

Generating a function control flow graph.

This example shows how to load a specimen into analysis space and generate a control flow graph for each function. First we include rose.h and then any additional binary analysis header files:

#include <rose.h>
#include <Diagnostics.h>
#include <Partitioner2/Engine.h>
#include <Partitioner2/GraphViz.h>
#include <Sawyer/CommandLine.h>
static const char* purpose = "obtains a function control flow graph from a binary specimen";
static const char* description =
"This tool disassembles the specified file and generates prints a control flow "
"graph to standard output for each function. It is intended as a demo of how to "
"obtain a function CFG; there are better ways to print graphs.";
using namespace Rose::Diagnostics;
using namespace Rose::BinaryAnalysis;

Then, in the main program, we create a disassembling and partitioning engine and use it to parse the command-line. This allows our tool to easily support the multitude of partitioner settings and container formats:

ROSE_INITIALIZE; // see Rose::initialize
Partitioner2::Engine engine;
std::vector<std::string> specimen = engine.parseCommandLine(argc, argv, purpose, description).unreachedArgs();
if (specimen.empty()) {
mlog[FATAL] <<"no binary specimen specified; see --help\n";
exit(1);
}

Next, now that the engine is configured and we know the name(s) or resources for the specimen, we can parse the specimen container, load the specimen into memory, disassemble, and discover functions. The results are stored in a Partitioner object:

Partitioner2::Partitioner partitioner = engine.partition(specimen);

Finally, we'll iterate over those functions to create function control flow graphs and print each graph. The cfg method returns a const reference to a global control flow graph, which normally serves as the starting point for many analyses. But in this case, we want only the subgraph that represents an individual function, so we copy the global CFG and then remove those vertices and edges that are uninteresting. This operation takes time that is linear with respect to the number of vertices and edges:

BOOST_FOREACH (const Partitioner2::Function::Ptr &function, partitioner.functions()) {
// global control flow graph
Partitioner2::ControlFlowGraph cfg = partitioner.cfg();
// Erase all vertices that don't belong to the function of interest, and their incident edges
Partitioner2::ControlFlowGraph::VertexIterator vi = cfg.vertices().begin();
while (vi != cfg.vertices().end()) {
if (!vi->value().isOwningFunction(function)) {
cfg.eraseVertex(vi++);
} else {
++vi;
}
}
// Print the results
std::cout <<"CFG for " <<function->printableName() <<"\n"
<<" Vertices:\n";
BOOST_FOREACH (const Partitioner2::ControlFlowGraph::Vertex &v, cfg.vertices())
std::cout <<" " <<partitioner.vertexName(v) <<"\n";
std::cout <<" Edges:\n";
BOOST_FOREACH (const Partitioner2::ControlFlowGraph::Edge &e, cfg.edges())
std::cout <<" " <<partitioner.edgeName(e) <<"\n";
}

The Partitioner2::DataFlow namespace has a buldDfCfg function that creates a slightly different kind of control flow graph–one that's more useful for data-flow–which also permits intra- and inter-procedural analysis based on user criteria.

Here's the entire program:

1 #include <rose.h>
3 
4 #include <Diagnostics.h>
5 #include <Partitioner2/Engine.h>
6 #include <Partitioner2/GraphViz.h>
7 #include <Sawyer/CommandLine.h>
8 
9 static const char* purpose = "obtains a function control flow graph from a binary specimen";
10 static const char* description =
11  "This tool disassembles the specified file and generates prints a control flow "
12  "graph to standard output for each function. It is intended as a demo of how to "
13  "obtain a function CFG; there are better ways to print graphs.";
14 
15 using namespace Rose::Diagnostics;
16 using namespace Rose::BinaryAnalysis;
18 
19 int
20 main(int argc, char *argv[]) {
22  ROSE_INITIALIZE; // see Rose::initialize
23  Partitioner2::Engine engine;
24  std::vector<std::string> specimen = engine.parseCommandLine(argc, argv, purpose, description).unreachedArgs();
25  if (specimen.empty()) {
26  mlog[FATAL] <<"no binary specimen specified; see --help\n";
27  exit(1);
28  }
30 
32  Partitioner2::Partitioner partitioner = engine.partition(specimen);
34 
36  BOOST_FOREACH (const Partitioner2::Function::Ptr &function, partitioner.functions()) {
37  // global control flow graph
38  Partitioner2::ControlFlowGraph cfg = partitioner.cfg();
39 
40  // Erase all vertices that don't belong to the function of interest, and their incident edges
41  Partitioner2::ControlFlowGraph::VertexIterator vi = cfg.vertices().begin();
42  while (vi != cfg.vertices().end()) {
43  if (!vi->value().isOwningFunction(function)) {
44  cfg.eraseVertex(vi++);
45  } else {
46  ++vi;
47  }
48  }
49 
50  // Print the results
51  std::cout <<"CFG for " <<function->printableName() <<"\n"
52  <<" Vertices:\n";
53  BOOST_FOREACH (const Partitioner2::ControlFlowGraph::Vertex &v, cfg.vertices())
54  std::cout <<" " <<partitioner.vertexName(v) <<"\n";
55  std::cout <<" Edges:\n";
56  BOOST_FOREACH (const Partitioner2::ControlFlowGraph::Edge &e, cfg.edges())
57  std::cout <<" " <<partitioner.edgeName(e) <<"\n";
58  }
60 }
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1894
Base class for engines driving the partitioner.
Definition: Engine.h:101
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:605
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1454
Messages that indicate an abnormal situation from which the program was unable to recover...
Definition: Message.h:329
static std::string vertexName(const ControlFlowGraph::Vertex &)
Name of a vertex.
static std::string edgeName(const ControlFlowGraph::Edge &)
Name of an edge.
Binary analysis.
virtual Partitioner partition(const std::vector< std::string > &fileNames=std::vector< std::string >())
Partition instructions into basic blocks and functions.
Sawyer::CommandLine::ParserResult parseCommandLine(int argc, char *argv[], const std::string &purpose, const std::string &description)
Parse the command-line.
std::vector< Function::Ptr > functions() const
All functions attached to the CFG/AUM.
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
Definition: Graph.h:1563
std::vector< std::string > unreachedArgs() const
Returns program arguments that were not reached during parsing.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:290
Controls diagnostic messages from ROSE.
Definition: Diagnostics.h:264

Generating a binary function call graph in GraphViz format.

This example is similar to the Hello, World! example, but demonstrates how to analyze function call information to construct a function call graph (CG) and then emit that graph as a GraphViz file. The output can be converted to a picture with the "dot" command, or visualized interactively with ZGRViewer.

#include <rose.h>
#include <Diagnostics.h>
#include <Partitioner2/Engine.h>
#include <Partitioner2/GraphViz.h>
#include <Sawyer/CommandLine.h>

As before, the "rose.h" header is the first of the ROSE headers to be included, followed by the binary analysis headers in any order.

using namespace Rose;
using namespace Rose::Diagnostics;
using namespace Rose::BinaryAnalysis;

This time we'll use a few namespaces to reduce our typing. The Rose::Diagnostics namespace brings into scope the diagnostic support (mlog and FATAL in this example) which is accessed through the "--log" or "-L" command-line switches and controls what kinds of debugging output is produced. If you run this program with "-L all" you'll get traces and debugging from all the ROSE components that use this mechanism; see "-L help" for info about fine tuning this.

struct Settings {
std::string outputName;
Settings()
: outputName("cg.dot") {}
};

Many of the binary analysis tools find that holding all command-line settings in a single struct is a convenient way to organize things. This example only has one tool-specific setting–the name of the output file for the call graph.

static std::vector<std::string>
parseCommandLine(int argc, char *argv[], Partitioner2::Engine &engine, Settings &settings) {
using namespace Sawyer::CommandLine;
std::string purpose = "obtains a function call graph from a binary specimen";
std::string description =
"This tool disassembles the specified file and generates a function call "
"graph named \"cg.dot\" in the current working directory. The dot file "
"can be processed with GraphViz commands or viewed directly with ZGRViewer.";
Parser parser = engine.commandLineParser(purpose, description);
SwitchGroup tool("Tool switches");
tool.insert(Switch("output", 'O')
.argument("filename", anyParser(settings.outputName))
.doc("Specifies the name of the call graph that is generated by "
"this tool. The default is \"" +
StringUtility::cEscape(settings.outputName) + "\""));
return parser.with(tool).parse(argc, argv).apply().unreachedArgs();
}

The Hello, World! example showed the simplest way to parse a command-line, but this time we'll do something a little more complex. This time we want to augment the command-line parser so it knows about the switches that this tool supports. The parser itself comes from the Sawyer library, part of which is distributed along with the ROSE source code. We obtain the default parser from the disassembly and partitioning engine, and augment it with a switch group containing the switches specific to this tool. Our "--output" or "-O" switch takes a single argument, a file name that can be any string. The "doc" property is the documentation for our switch and will appear in the Unix man page produced by running with "--help". Finally, we invoke the parser with our additional switch group on the argument list in argv. If the parsing is successful we apply the results to our settings and then return the rest of the command line (probably information about the specimen).

ROSE_INITIALIZE;
Settings settings;
Partitioner2::Engine engine;
std::vector<std::string> specimen = parseCommandLine(argc, argv, engine, settings);
if (specimen.empty()) {
mlog[FATAL] <<"no binary specimen specified; see --help\n";
exit(1);
}

In the main program we initialize our settings and instantiate a disassembly/partitioning engine, then parse the command-line and get the list of non-switch arguments. If there are none, give the user some help; this is often an indication that the user invoked the command with no arguments at all in order to get an error message that hopefully contains some usage hints.

Partitioner2::Partitioner partitioner = engine.partition(specimen);

Instead of calling engine.frontend, this time we call engine.partition in order to get access to the partitioning analysis results. No AST is created in this case, although we could get one if we wanted by querying the engine for it. The data structures used by the partitioner are much more efficiently tuned for analysis than an AST, so we'll stick with the partitioner.

Partitioner2::FunctionCallGraph callgraph = partitioner.functionCallGraph(false);

The partitioner knows how to construct a call graph from its internal data structures. The FunctionCallGraph class can also be manipulated directly. Now's a good time to point out that many binary analysis data structures use pointers to shared objects. The objects are reference counted and deleted automatically. Classes that are used in this way do not have public constructors, but rather instance methods (and sometimes additional factories as well) that allocate and initialize the object and return a smart pointer. In this example, if we were to delete the partitioner or engine the callgraph would still point to valid functions, which still point to valid instructions, etc.

std::ofstream output(settings.outputName.c_str());
Partitioner2::GraphViz::CgEmitter emitter(partitioner, callgraph);
emitter.emitCallGraph(output);

Finally we can emit the call graph as a GraphViz file. This is done through a CgEmitter that specializes a more general GraphViz emitter. The emitter API allows you to fine tune the output by adjusting colors and other GraphViz edge and vertex properties.

Here's the full listing. Compile it using the same instructions as for the Hello, World! example.

1 #include <rose.h>
3 
4 #include <Diagnostics.h>
5 #include <Partitioner2/Engine.h>
6 #include <Partitioner2/GraphViz.h>
7 #include <Sawyer/CommandLine.h>
9 
11 using namespace Rose;
12 using namespace Rose::Diagnostics;
13 using namespace Rose::BinaryAnalysis;
15 
17 struct Settings {
18  std::string outputName;
19 
20  Settings()
21  : outputName("cg.dot") {}
22 };
24 
26 static std::vector<std::string>
27 parseCommandLine(int argc, char *argv[], Partitioner2::Engine &engine, Settings &settings) {
28  using namespace Sawyer::CommandLine;
29 
30  std::string purpose = "obtains a function call graph from a binary specimen";
31  std::string description =
32  "This tool disassembles the specified file and generates a function call "
33  "graph named \"cg.dot\" in the current working directory. The dot file "
34  "can be processed with GraphViz commands or viewed directly with ZGRViewer.";
35 
36  Parser parser = engine.commandLineParser(purpose, description);
37 
38  SwitchGroup tool("Tool switches");
39  tool.insert(Switch("output", 'O')
40  .argument("filename", anyParser(settings.outputName))
41  .doc("Specifies the name of the call graph that is generated by "
42  "this tool. The default is \"" +
43  StringUtility::cEscape(settings.outputName) + "\""));
44 
45  return parser.with(tool).parse(argc, argv).apply().unreachedArgs();
46 }
48 
49 int
50 main(int argc, char *argv[]) {
52  ROSE_INITIALIZE;
53  Settings settings;
54  Partitioner2::Engine engine;
55  std::vector<std::string> specimen = parseCommandLine(argc, argv, engine, settings);
56  if (specimen.empty()) {
57  mlog[FATAL] <<"no binary specimen specified; see --help\n";
58  exit(1);
59  }
61 
63  Partitioner2::Partitioner partitioner = engine.partition(specimen);
65 
67  Partitioner2::FunctionCallGraph callgraph = partitioner.functionCallGraph(false);
69 
71  std::ofstream output(settings.outputName.c_str());
72  Partitioner2::GraphViz::CgEmitter emitter(partitioner, callgraph);
73  emitter.emitCallGraph(output);
75 }
FunctionCallGraph functionCallGraph(bool allowParallelEdges=true) const
Returns a function call graph.
virtual Sawyer::CommandLine::Parser commandLineParser(const std::string &purpose, const std::string &description)
Creates a command-line parser.
Base class for engines driving the partitioner.
Definition: Engine.h:101
Describes one command-line switch.
Definition: CommandLine.h:1960
A collection of related switch declarations.
Definition: CommandLine.h:2488
Main namespace for the ROSE library.
Messages that indicate an abnormal situation from which the program was unable to recover...
Definition: Message.h:329
AnyParser< T >::Ptr anyParser(T &storage)
Factory for value parsers.
Definition: CommandLine.h:1387
Switch & doc(const std::string &s)
Property: detailed description.
Definition: CommandLine.h:2104
Parser & with(const SwitchGroup &sg)
Add switch declarations.
Definition: CommandLine.h:2712
ROSE_UTIL_API std::string cEscape(const std::string &)
Escapes characters that are special to C/C++.
The parser for a program command line.
Definition: CommandLine.h:2674
Binary analysis.
Parses program command line switches and arguments.
Definition: CommandLine.h:161
virtual Partitioner partition(const std::vector< std::string > &fileNames=std::vector< std::string >())
Partition instructions into basic blocks and functions.
const ParserResult & apply() const
Saves parsed values in switch-specified locations.
ParserResult parse(int argc, char *argv[])
Parse program arguments.
std::vector< std::string > unreachedArgs() const
Returns program arguments that were not reached during parsing.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:290
Controls diagnostic messages from ROSE.
Definition: Diagnostics.h:264

Finding static strings in a binary specimen

This example parses and disassembles a binary specimen and search for all static strings, similar to the Unix "strings" command. This simple example can be a starting point for a more in depth strings analysis than what's possible with the Unix command.

#include <rose.h>
#include <boost/foreach.hpp>
#include <Partitioner2/Engine.h>
#include <BinaryString.h>
using namespace Rose;
using namespace Rose::BinaryAnalysis;

Include headers. The "rose.h" must always be before other ROSE headers.

ROSE_INITIALIZE; // see Rose::initialize
std::string purpose = "finds static strings in a binary specimen";
std::string description =
"This tool disassembles a binary specimen and then scans the "
"read-only parts of memory to find static strings. It looks for "
"C-style NUL-termianted printable ASCII strings, zero-terminated "
"UTF-16 little-endian strings, two-byte little-endian length-encoded "
"ASCII strings, and some other common formats.";
Partitioner2::Engine engine;
std::vector<std::string> specimen =
engine.parseCommandLine(argc, argv, purpose, description).unreachedArgs();

Yet another way to parse a command-line. This time we're trying to avoid calling Partitioner2::Engine::frontend because we don't actually need to disassemble or partition anything–string searching operates on raw memory rather than instructions, so we can save some time.

MemoryMap::Ptr map = engine.loadSpecimens(specimen);
ByteOrder::Endianness sex = engine.obtainDisassembler()->byteOrder();

The engine.loadSpecimens method parses the speicmen container if present (e.g., Linux ELF) and determines how the specimen should be mapped into memory. The result is a MemoryMap that describes memory segments with addresses, permissions, names, etc. Try inserting a call to MemoryMap::dump here to get an idea of what it contains.

The byte order will be needed by the string decoder in order to know how to decode the multi-byte length fields. We could have gotten this same information any number of other ways, but this is the most convenient in this situation. Note that knowledge of the byte order depends upon knowledge of the specimen architecture even though we don't actually need to disassemble anything.

Strings::StringFinder finder; // the string analyzer
finder.settings().minLength = 5; // no strings shorter than 5 characters
finder.settings().maxLength = 8192; // no strings longer than 8k characters
finder.insertCommonEncoders(sex); // match common encodings of strings
finder.find(map->require(MemoryMap::READABLE).prohibit(MemoryMap::WRITABLE));

Here we perform the string searching. Most binary analysis algorithms are packaged into a class. The idea is that one instantiates the analyzer, configures it, calls some method to perform the analysis (here it's find), and then queries the results.

The MemoryMap::require and MemoryMap::prohibit methods are a form of filtering. They're filtering the memory map so that the string analyzer only sees memory that's readable but not writable.

// Output, or just do "std::cout <<finder" if you're not picky.
BOOST_FOREACH (const Strings::EncodedString &string, finder.strings()) {
std::cout <<"string at " <<string.address() <<" for " <<string.size() <<" bytes\n";
std::cout <<"encoding: " <<string.encoder()->name() <<"\n";
std::cout <<"narrow value: \"" <<StringUtility::cEscape(string.narrow()) <<"\"\n";
}

Generating the output is a matter of iterating over the strings that were found and printing some information. Most analyzer objects also know how to print themselves although those defaults are not always suitable for a polished tool.

Here's the entire program:

1 #include <rose.h>
3 
4 #include <boost/foreach.hpp>
5 #include <Partitioner2/Engine.h>
6 #include <BinaryString.h>
7 
8 using namespace Rose;
9 using namespace Rose::BinaryAnalysis;
11 
12 int
13 main(int argc, char *argv[]) {
15  ROSE_INITIALIZE; // see Rose::initialize
16  std::string purpose = "finds static strings in a binary specimen";
17  std::string description =
18  "This tool disassembles a binary specimen and then scans the "
19  "read-only parts of memory to find static strings. It looks for "
20  "C-style NUL-termianted printable ASCII strings, zero-terminated "
21  "UTF-16 little-endian strings, two-byte little-endian length-encoded "
22  "ASCII strings, and some other common formats.";
23 
24  Partitioner2::Engine engine;
25  std::vector<std::string> specimen =
26  engine.parseCommandLine(argc, argv, purpose, description).unreachedArgs();
28 
30  MemoryMap::Ptr map = engine.loadSpecimens(specimen);
31  ByteOrder::Endianness sex = engine.obtainDisassembler()->byteOrder();
33 
35  Strings::StringFinder finder; // the string analyzer
36  finder.settings().minLength = 5; // no strings shorter than 5 characters
37  finder.settings().maxLength = 8192; // no strings longer than 8k characters
38  finder.insertCommonEncoders(sex); // match common encodings of strings
39  finder.find(map->require(MemoryMap::READABLE).prohibit(MemoryMap::WRITABLE));
41 
43  // Output, or just do "std::cout <<finder" if you're not picky.
44  BOOST_FOREACH (const Strings::EncodedString &string, finder.strings()) {
45  std::cout <<"string at " <<string.address() <<" for " <<string.size() <<" bytes\n";
46  std::cout <<"encoding: " <<string.encoder()->name() <<"\n";
47  std::cout <<"narrow value: \"" <<StringUtility::cEscape(string.narrow()) <<"\"\n";
48  }
50 }
virtual Disassembler * obtainDisassembler(Disassembler *hint=NULL)
Obtain a disassembler.
size_t minLength
Minimum length of matched strings.
Definition: BinaryString.h:812
Base class for engines driving the partitioner.
Definition: Engine.h:101
const Settings & settings() const
Property: Analysis settings often set from a command-line.
Definition: BinaryString.h:862
Analysis to find encoded strings.
Definition: BinaryString.h:802
Main namespace for the ROSE library.
AddressMapConstraints< const AddressMap > require(unsigned x) const
Constraint: required access bits.
Definition: AddressMap.h:1028
StringFinder & find(const MemoryMap::ConstConstraints &, Sawyer::Container::MatchFlags flags=0)
Finds strings by searching memory.
ByteOrder::Endianness byteOrder() const
Property: Byte order of instructions in memory.
Definition: Disassembler.h:212
ROSE_UTIL_API std::string cEscape(const std::string &)
Escapes characters that are special to C/C++.
size_t maxLength
Maximum length of matched strings.
Definition: BinaryString.h:818
const std::vector< EncodedString > & strings() const
Obtain strings that were found.
Definition: BinaryString.h:960
Binary analysis.
StringFinder & insertCommonEncoders(ByteOrder::Endianness)
Inserts common encodings.
Sawyer::CommandLine::ParserResult parseCommandLine(int argc, char *argv[], const std::string &purpose, const std::string &description)
Parse the command-line.
virtual MemoryMap::Ptr loadSpecimens(const std::vector< std::string > &fileNames=std::vector< std::string >())
Load and/or link interpretation.
std::vector< std::string > unreachedArgs() const
Returns program arguments that were not reached during parsing.

Graph dominators and post dominators

Loosely speaking, the dominator of a vertex of a graph is another vertex that's visited on every path from some starting vertex to the vertex in question. Most of the time, we're interested in an immediate dominator, which is the closest dominator to the vertex in question. A more rigorous definition can be found in Wikipedia, among other places. Post-dominators are similar in that a post dominator of a vertex is some other vertex that's visited on every path from the vertex in question to some ending vertex.

ROSE uses the Sawyer Graph API for all binary analysis graphs, and Sawyer has functions for calculating dominators and post-dominators. The following example is a tool that finds the dominator for each vertex in the control flow graph of each function.

static const char *programPurpose = "prints dominators for all function CFGs";
static const char *programDescription =
"The purpose of this tool is to demonstrate how to calculate dominators (and by extension, post-dominators) for all "
"vertices of a function control flow graph (and by extension, any Sawyer graph). It parses, loads, disassembles, and "
"partitions a binary specimen and then iterates over the functions. For each function, it obtains a function CFG, "
"calculates the immediate dominator for each vertex, and shows the results.";
#include <rose.h>
#include <Partitioner2/Engine.h>
#include <Partitioner2/Partitioner.h>
#include <Sawyer/GraphAlgorithm.h>

The first step, above, is to include the appropriate declarations. Our convention for writing tools is to describe the tool with a couple of strings that appear at the very top of the source code. These strings are used later in the program to generate the documentation for the "--help" output.

This tool is so simple that everything else is in "main". First we initialize things:

int
main(int argc, char *argv[])
{
ROSE_INITIALIZE;
P2::Engine engine;
engine.doingPostAnalysis(false); // not needed for this tool, and faster without
std::vector<std::string> specimen = engine.parseCommandLine(argc, argv, programPurpose, programDescription).unreachedArgs();
P2::Partitioner partitioner = engine.partition(specimen);

The ROSE_INITIALIZE macro is always the first ROSE-related statement and checks that this tool was compiled with header files that are binary compatible with the ROSE library. Then we create a partitioning engine to parse the command-line to get the specimen resources. The specimen is some combination of a ELF or PE file name, raw memory dumps, S-Records, and/or process IDs. The engine.partition call does all the hard work of parsing containers, loading data into the virtual address space, decoding CPU instructions, and creating basic blocks and functions. It returns a partitioner object that stores all the results, which include a global control flow graph.

Then we iterate over the functions:

BOOST_FOREACH (P2::Function::Ptr function, partitioner.functions()) {
std::cout <<"CFG dominators for " <<function->printableName() <<":\n";

We want to create a function CFG, but all we have from the partitioner is a global CFG. We can use the fact that a function CFG is a subset of the global CFG and therefore create the function CFG by copying the global CFG and removing all vertices and edges that are not part of the function CFG. Although this isn't the most efficient way to create function CFGs in a loop over all functions, it is very simple.

We'll need to know the entry vertex of the function's CFG:

P2::ControlFlowGraph cfg = partitioner.cfg();
P2::ControlFlowGraph::VertexIterator entryVertex = cfg.findVertex(partitioner.findPlaceholder(function->address())->id());

We found the entry vertex in the function CFG by first finding it in the global CFG and then using a feature of Sawyer graphs, namely, when a graph is copied its vertices and edges have the same IDs as those in the source graph, and we can obtain a vertex pointer (iterator) in constant time if we know its ID. We have to convert the ID to a vertex pointer before removing the non-function vertices because IDs are not stable across erase operations, but iterators are.

Next we erase the non-function vertices and edges:

P2::ControlFlowGraph::VertexIterator vi = cfg.vertices().begin();
while (vi != cfg.vertices().end()) {
if (!vi->value().isOwningFunction(function)) { // a basic block can belong to multiple functions
ASSERT_forbid(vi == entryVertex);
cfg.eraseVertex(vi++);
} else {
++vi;
}
}

This is the simple way to build a function CFG from a global CFG. It's important to use a post-increment in the eraseVertex call. Since we're inside a loop iterating over every function, a more efficient implementation would have created all the function CFGs in a single pass over the global CFG. As of June 2017, ROSE does not have functions for returning function CFGs – it only has a global CFG – because there are many details that need to be considered depending on the situation (e.g., function calls and returns are two cases that typically need massaging in a function CFG depending on the purpose of the CFG).

Finally, we get to the real meat of this example: finding the immediate dominator for every vertex in the function CFG given the CFG's entry vertex:

std::vector<P2::ControlFlowGraph::VertexIterator> idoms = Sawyer::Container::Algorithm::graphDominators(cfg, entryVertex);

The graphDominators function can handle any type of Sawyer graph, thus we could also pass a function call graph or a data-flow graph.

The return value is a vector indexed by vertex ID, whose values point to either the corresponding immediate dominator or the vertex end iterator (not all vertices have an immediate dominator). Using a vector indexed by vertex ID is an idiom used throughout ROSE whenever we need to associated extra data with an existing graph. Since a vertex pointer (iterator) can be converted to a vertex ID in constant time, and indexing into the vector is constant time, we can always find the extra data in constant time. And since vertex IDs are consecutive integers beginning at zero, this is also a space-efficient way to represent data that's present for most, if not all, vertices.

Finally, let us iterate over the results to print them:

for (size_t i=0; i<idoms.size(); ++i) {
std::cout <<" dominator of " <<P2::Partitioner::vertexName(*cfg.findVertex(i)) <<" is ";
if (cfg.isValidVertex(idoms[i])) {
std::cout <<P2::Partitioner::vertexName(*idoms[i]) <<"\n";
} else {
std::cout <<"none\n";
}
}

Since vector indexes are equivalent to vertex IDs, we can obtain a vertex with a constant-time findVertex call and a constant-time iterator dereference. Since this is a CFG from the partitioner (or at least a copy thereof), we can use the vertexName static method to print some info about it. Using the static method (that takes a vertex value) is important; the non-static method (that takes a vertex iterator) will think that we're handing it a pointer to some vertex in the partitioner's own global CFG.

Here's the entire program:

1 // Extensive documentation for this program is in the Binary Analysis Tutorial in doxygen.
2 // Do not change the output format -- this tool is also used by tests/nonsmoke/functional/BinaryAnalysis
3 
5 static const char *programPurpose = "prints dominators for all function CFGs";
6 static const char *programDescription =
7  "The purpose of this tool is to demonstrate how to calculate dominators (and by extension, post-dominators) for all "
8  "vertices of a function control flow graph (and by extension, any Sawyer graph). It parses, loads, disassembles, and "
9  "partitions a binary specimen and then iterates over the functions. For each function, it obtains a function CFG, "
10  "calculates the immediate dominator for each vertex, and shows the results.";
11 
12 #include <rose.h>
13 #include <Partitioner2/Engine.h>
14 #include <Partitioner2/Partitioner.h>
15 #include <Sawyer/GraphAlgorithm.h>
16 
19 
21 int
22 main(int argc, char *argv[])
23 {
24  ROSE_INITIALIZE;
25  P2::Engine engine;
26  engine.doingPostAnalysis(false); // not needed for this tool, and faster without
27  std::vector<std::string> specimen = engine.parseCommandLine(argc, argv, programPurpose, programDescription).unreachedArgs();
28  P2::Partitioner partitioner = engine.partition(specimen);
30 
32  BOOST_FOREACH (P2::Function::Ptr function, partitioner.functions()) {
33  std::cout <<"CFG dominators for " <<function->printableName() <<":\n";
35 
37  P2::ControlFlowGraph cfg = partitioner.cfg();
38  P2::ControlFlowGraph::VertexIterator entryVertex = cfg.findVertex(partitioner.findPlaceholder(function->address())->id());
40  ASSERT_require(cfg.isValidVertex(entryVertex));
41 
43  P2::ControlFlowGraph::VertexIterator vi = cfg.vertices().begin();
44  while (vi != cfg.vertices().end()) {
45  if (!vi->value().isOwningFunction(function)) { // a basic block can belong to multiple functions
46  ASSERT_forbid(vi == entryVertex);
47  cfg.eraseVertex(vi++);
48  } else {
49  ++vi;
50  }
51  }
53 
55  std::vector<P2::ControlFlowGraph::VertexIterator> idoms = Sawyer::Container::Algorithm::graphDominators(cfg, entryVertex);
57  ASSERT_require(idoms.size() == cfg.nVertices());
58 
60  for (size_t i=0; i<idoms.size(); ++i) {
61  std::cout <<" dominator of " <<P2::Partitioner::vertexName(*cfg.findVertex(i)) <<" is ";
62  if (cfg.isValidVertex(idoms[i])) {
63  std::cout <<P2::Partitioner::vertexName(*idoms[i]) <<"\n";
64  } else {
65  std::cout <<"none\n";
66  }
67  }
69  }
70 }
Binary function detection.
std::vector< typename GraphTraits< Graph >::VertexIterator > graphDominators(Graph &g, typename GraphTraits< Graph >::VertexIterator root)
Find immediate pre-dominators.

Next steps

Most binary analysis capabilities are documented in the Rose::BinaryAnalysis namespace. The test directory, "$ROSE_SOURCE/tests/nonsmoke/functional/roseTests/BinaryTests", also has many examples, some of which are slightly hard to read since there main purpose is to test rather than demonstrate. The "$ROSE_SOURCE/projects/BinaryAnalysisTools" directory (as well as some other project directories) has real programs that use the binary analysis interface.