Updated ParseAPI manual to include header information in class descriptions.
[dyninst.git] / parseAPI / doc / parseapi.tex
1 \documentclass{article}
2
3 \usepackage{booktabs}
4 \usepackage{color}
5 \usepackage{pgf}
6 \usepackage{tikz}
7 \usetikzlibrary{arrows,positioning,fit,shapes,decorations,decorations.pathmorphing,decorations.pathreplacing,calc,patterns,scopes,matrix}
8 \pgfrealjobname{parseapi}
9
10 \usepackage{helvet}
11 \usepackage{enumitem}
12 \usepackage[letterpaper]{geometry}
13 \usepackage{listings}
14 \usepackage{verbatim}
15 \usepackage[T1]{fontenc}
16
17 \setlength{\parindent}{0.0in}
18 \setlength{\parskip}{0.1in}
19
20 \newenvironment{apient}{\small\verbatim}{\endverbatim}
21
22 \newcommand{\apidesc}[1]{%
23 {\addtolength{\leftskip}{4em}%
24 #1\par\medskip}
25 }
26
27 \newcommand{\definedin}[1]{%
28 \textbf{Defined in:} \texttt{#1}
29 }
30
31 \begin{document}
32 \thispagestyle{empty}
33
34 \begin{titlepage}
35 \beginpgfgraphicnamed{titlepage}
36 \begin{tikzpicture}[remember picture, overlay]
37     \path
38         (current page.north west) coordinate (origin)
39         (current page.north) coordinate (topcenter);
40
41     % Header
42     \node [font=\sffamily] (pppt) at ($(topcenter) - (0,1.0in)$) 
43         {\fontsize{24}{36}\selectfont Paradyn Parallel Performance Tools};
44
45     % Document Title
46 % older versions of pgf have a bug for matrices in overlay mode;
47 % have to specify positions manually
48 %    \matrix (Title) [%
49 %        matrix of nodes,%
50 %        nodes={font=\sffamily,right},%
51 %        matrix anchor=west,%
52 %        row sep=12pt
53 %        ] at ($(origin)+(0.75in,-3.0in)$)
54 %    {
55 %        \fontsize{48}{56}\selectfont ParseAPI \\
56 %        \fontsize{44}{56}\selectfont Programmer's Guide \\
57 %    };
58
59     \node [anchor=west,font=\sffamily] (title1) at ($(origin)+(0.75in,-3.0in)$)
60         {\fontsize{48}{56}\selectfont ParseAPI};
61     \node [anchor=west,font=\sffamily] (title2) at ($(title1.west)+(0in,-56pt)$)
62         {\fontsize{48}{56}\selectfont Programmer's Guide};
63
64     % Release information
65 %    \matrix (Releaseinfo) [%
66 %        matrix of nodes,%
67 %        nodes={font=\sffamily,right},%
68 %        matrix anchor=west,%
69 %        row sep=8pt
70 %        ] at ($(origin)+(0.75in,-5.0in)$)
71 %    {
72 %        %\fontsize{24}{32}\selectfont Release 0.1 \\
73 %        \fontsize{24}{32}\selectfont Beta Release \\
74 %        \fontsize{24}{32}\selectfont Oct 2010 \\
75 %    };
76
77     \node [anchor=west,font=\sffamily] (rel1) at ($(origin)+(0.75in,-5.0in)$)
78         {\fontsize{24}{32}\selectfont 7. 0 Release};
79     \node [anchor=west,font=\sffamily] (rel2) at ($(rel1.west)+(0in,-32pt)$)
80         {\fontsize{24}{32}\selectfont Mar 2011};
81
82     % Contact information
83 %    \matrix (UWaddress) [%
84 %        matrix of nodes,%
85 %        nodes={font=\sffamily\large,right},%
86 %        matrix anchor=north west
87 %        ] at ($(origin)+(0.75in,-7in)$)
88 %    {
89 %        Computer Science Department \\
90 %        University of Wisconsin--Madison \\
91 %        Madison, WI 53711 \\
92 %    };
93
94     \node [anchor=west,font=\sffamily\large] (uw1) at ($(origin)+(0.75in,-7.0in)$)
95         {Computer Science Department};
96     \node [anchor=west,font=\sffamily\large] (uw2) at ($(uw1.west)+(0in,-20pt)$)
97         {University of Wisconsin--Madison};
98     \node [anchor=west,font=\sffamily\large] (uw3) at ($(uw2.west)+(0in,-20pt)$)
99         {Madison, WI 53711};
100
101
102 %    \matrix (UMDaddress) [%
103 %        matrix of nodes,%
104 %        nodes={font=\sffamily\large,right},%
105 %        matrix anchor=north west,
106 %        below=1em of UWaddress.south west
107 %        ]
108 %    {
109 %        Computer Science Department \\
110 %        University of Maryland \\
111 %        College Park, MD 20742 \\
112 %    };
113
114     \node [anchor=west,font=\sffamily\large] (umd1) at ($(uw3.south west)+(0in,-2.5em)$)
115         {Computer Science Department};
116     \node [anchor=west,font=\sffamily\large] (umd2) at ($(umd1.west)+(0in,-20pt)$)
117         {University of Maryland};
118     \node [anchor=west,font=\sffamily\large] (umd3) at ($(umd2.west)+(0in,-20pt)$)
119         {College Park, MD 20742};
120
121 %    \matrix (Emails) [%
122 %        matrix of nodes,%
123 %        nodes={font=\sffamily,right},%
124 %        matrix anchor=north west,%
125 %        below=1em of UMDaddress.south west,%
126 %        anchor=base
127 %        ]
128 %    {
129 %        Email & \texttt{bugs@dyninst.org} \\
130 %        Web & \texttt{www.dyninst.org} \\
131 %    };
132
133     \node [anchor=west,font=\sffamily] (email1) at ($(umd3.south west)+(-0.5em,-2.5em)$)
134         %{Email \texttt{bugs@dyninst.org}};
135         {\begin{tabular}{ll}%
136          Email & \texttt{bugs@dyninst.org} \\
137          Web & \texttt{www.dyinst.org} \\
138         \end{tabular}};
139         
140
141     % Logo
142     \path 
143         node (logo) at ($(origin)+(4.0in,-7.0in)$) [%
144             anchor=north west]
145         {%
146             \includegraphics[width=3.25in]{paradyn_logo}
147         }; 
148
149
150 \end{tikzpicture}
151 \endpgfgraphicnamed
152 \end{titlepage}
153
154 \tableofcontents
155 \clearpage
156
157 \section{Introduction}
158 \label{sec:intro}
159
160 A binary code parser converts the machine code representation of a program,
161 library, or code snippet to abstractions such as the instructions, basic
162 blocks, and functions that the binary code represents. The ParseAPI is a
163 multi-platform library for creating such abstractions from binary code sources.
164 The current incarnation uses the Dyninst SymtabAPI as the default binary code
165 source; all platforms and architectures handled by the SymtabAPI are supported.
166 The ParseAPI is designed to be easily extensible to other binary code sources.
167 Support for parsing binary code in memory dumps or other formats requires only
168 implementation of a small interface as described in this document.
169
170 This API provides the user with a control flow-oriented view of a binary code
171 source. Each code object such as a program binary or library is represented as
172 a top-level collection containing the functions, basic blocks, and edges that
173 represent the control flow graph. A simple query interface is provided for
174 retrieving lower level objects like functions and basic blocks through address
175 or other attribute lookups. These objects can be used to navigate the program
176 structure as described below.
177
178 \emph{The ParseAPI is currently released as a public beta. The interfaces
179 described in this manual are subject to change in future versions. Feedback and
180 comments are welcome; please email bugs@dyninst.org.}
181
182 \section{Abstractions}
183 \label{sec:abstractions}
184
185 The basic representation of code in this API is the control flow
186 graph (CFG). Binary code objects are represented as regions of contiguous bytes that, when parsed, form the nodes and edges of this graph. The following abstractions make up this CFG-oriented representation of binary code:
187
188 % CFG representation abastractions
189 %
190 % Function, Block, and Edge
191 \begin{itemize}[leftmargin=0pt,label=$\circ$]
192
193
194 {\item {\scshape block}: Nodes in the CFG represent \emph{basic blocks}:
195 straight line sequences of instructions $I_i \ldots I_j$ where for each $i < k
196 \le j$, $I_k$ postdominates $I_{k-1}$. Importantly, on some instruction set architectures basic blocks can \emph{overlap} on the same address range---variable length instruction sets allow for multiple interpretations of the bytes making up the basic block.
197 }
198
199 {\item {\scshape edge}: Typed edges beween the nodes in the CFG represent
200 execution control flow, such as conditional and unconditional branches,
201 fallthrough edges, and calls and returns. The graph therefore represents both
202 \emph{inter-} and \emph{intraprocedural} control flow: travseral of nodes and
203 edges can cross the boundaries of the higher level abstractions like
204 \emph{functions}.
205 }
206
207 {\item {\scshape function}: The \emph{function} is the primary semantic grouping of code in the binary, mirroring the familiar abstraction of procedural languages like C. Functions represent the set of all basic blocks reachable from a \emph{function entry point} through intraprocedural control flow only (that is, no calls or returns). Function entry points are determined in a variety of ways, such as hints from debugging symbols and recursive traversal along call edges.
208 }
209
210 \end{itemize}
211
212 % binary code representation abstractions
213 %
214 % code object, code source, and instruction source
215 \begin{itemize}[leftmargin=0pt,label=$\circ$]
216
217 {\item {\scshape code object}: A collection of distinct code regions are represented as a single code object, such as an executable or library. Code objects can normally be thought of as a single, discontiguous unique address space. However, the ParseAPI supports code objects in which the different regions have overlapping address spaces, such as UNIX archive files containing unlinked code.
218 }% end code object
219
220 {\item {\scshape instruction source}: An instruction source describes a backing store containing binary code. A binary file, a library, a memory dump or a process's executing memory image can all be described as an instruction source, allowing parsing of a variety of binary code objects.
221 }% end instruction source
222
223 {\item {\scshape code source}: The code source implements the instruction source interface, exporting methods that can access the underlying bytes of the binary code for parsing. It also exports a number of additional helper methods that do things such as returning the location of structured exception handling routines and function symbols. Code sources are tailored to particular binary types; the ParseAPI provides a SymtabAPI-based code source that understands ELF, COFF and PE file formats.
224 }% end code source
225
226 \end{itemize}
227
228 \section{A simple example}
229 \label{sec:example}
230
231 The following complete example uses the ParseAPI to parse a binary and dump its control flow graph in the Graphviz file format.
232
233 \lstset{language=[GNU]C++,basicstyle=\fontfamily{fvm}\selectfont\small}
234 \lstset{numbers=left, numberstyle=\tiny, stepnumber=5, numbersep=5pt}
235 \lstset{showstringspaces=false}
236 \lstinputlisting{example.cc}
237
238 \section{The Parsing API}
239 \label{sec:api}
240
241 \subsection{Class CodeObject}
242
243 \definedin{CodeObject.h}
244
245 The CodeObject class describes an individual binary code object, such as an
246 executable or library. It is the top-level container for parsing the object as
247 well as accessing that parse data. The following API routines and data types
248 are provided to support parsing and retrieving parsing products.
249
250 \begin{apient}
251 typedef ContainerWrapper<vector<Function*>,Function*,Function*> funclist
252 \end{apient}
253 \apidesc{Container for access to functions. Refer to Section \ref{sec:containers} for details. Library users \emph{must not} rely on the underlying container type of ContainerWrapper lists, as it is subject to change.}
254
255 \begin{apient}
256 CodeObject(CodeSource * cs,
257     CFGFactory * fact = NULL,
258     ParseCallback * cb = NULL,
259     bool defensiveMode = false)
260 \end{apient}
261 \apidesc{Constructs a new CodeObject from the provided CodeSource and
262 optional object factory and callback handlers. Any parsing hints provided
263 by the CodeSource are processed, but the binary is not parsed when this
264 constructor returns.
265
266 \medskip\noindent The \texttt{defensiveMode}
267 parameter optionally trades off coverage for safety; this mode is not
268 recommended for most applications as it makes very conservative assumptions
269 about control flow transfer instructions (see Section \ref{sec:defmode}.}
270
271 \begin{apient}
272 void parse()
273 \end{apient}
274 \apidesc{Recursively parses the binary represented by this CodeObject from all
275 known function entry points (i.e., the hints provided by the CodeSource). This
276 method and the following parsing methods may safely be invoked repeatedly if
277 new information about function locations is provided through the CodeSource.}
278
279 \begin{apient}
280 void parse(Address target, bool recursive)
281 \end{apient}
282 \apidesc{Parses the binary starting with the instruction at the provided target address. If \texttt{recursive} is {\scshape true}, recursive traversal parsing is used as in the default \texttt{parse()} method; otherwise only instructions reachable through intraprocedural control flow are visited.}
283
284 \begin{apient}
285 void parseGaps(CodeRegion *cr)
286 \end{apient}
287 \apidesc{Speculatively parse the indicated region of the binary using pattern matching to find likely function entry points. Only enabled on the x86 32-bit platform.}
288
289 \begin{apient}
290 Function * findFuncByEntry(CodeRegion * cr, Address entry)
291 \end{apient}
292 \apidesc{Find the function starting at address \texttt{entry} in the indicated CodeRegion. Returns {\scshape null} if no such function exists.}
293
294 \begin{apient}
295 int findFuncs(CodeRegion * cr, Address addr, std::set<Function*> & funcs)
296 \end{apient}
297 \apidesc{Finds all functions spanning \texttt{addr} in the code region, adding each to \texttt{funcs}. The number of results of this stabbing query are returned.}
298
299 \begin{apient}
300 int findFuncs(CodeRegion * cr, Address start, Address end, std::set<Function*> & funcs)
301 \end{apient}
302 \apidesc{Finds all functions overlapping the range \texttt{[start,end)} in the code region, adding each to \texttt{funcs}. The number of results of this stabbing query are returned.}
303
304 \begin{apient}
305 funclist & funcs()
306 \end{apient}
307 \apidesc{Returns a reference to a container of all functions in the binary. Refer to Section \ref{sec:containers} for container access details.}
308
309 \begin{apient}
310 Block * findBlockByEntry(CodeRegion * cr, Address entry)
311 \end{apient}
312 \apidesc{Find the basic block starting at address \texttt{entry}. Returns {\scshape null} if no such block exists.}
313
314 \begin{apient}
315 int findBlocks(CodeRegion * cr, Address addr, std::set<Block*> & blocks)
316 \end{apient}
317 \apidesc{Finds all blocks spanning \texttt{addr} in the code region, adding each to \texttt{blocks}. Multiple blocks can be returned only on platforms with variable-length instruction sets (such as IA32) for which overlapping instructions are possible; at most one block will be returned on all other platforms.}
318
319 \begin{apient}
320 void finalize()
321 \end{apient}
322 \apidesc{Force complete parsing of the CodeObject; parsing operations are otherwise completed only as needed to answer queries.}
323
324 \begin{apient}
325 CodeSource * cs()
326 \end{apient}
327 \apidesc{Return a reference to the underlying CodeSource.}
328
329 \begin{apient}
330 CFGFactory * fact()
331 \end{apient}
332 \apidesc{Return a reference to the CFG object factory.}
333
334 \subsection{Class CodeSource}
335 \label{sec:codesource}
336
337 \definedin{CodeSource.h}
338
339 The CodeSource interface is used by the ParseAPI to retrieve binary code from
340 an executable, library, or other binary code object; it also can provide hints
341 of function entry points (such as those derived from debugging symbols) to seed
342 the parser. The ParseAPI provides a default implementation based on the
343 SymtabAPI that supports many common binary formats. For details on implementing
344 a custom CodeSource, see Appendix \ref{sec:extend}.
345
346 \begin{apient}
347 virtual bool nonReturning(Address func_entry)
348 virtual bool nonReturning(std::string func_name)
349 \end{apient}
350 \apidesc{Looks up whether a function returns (by name or location). This information may be statically known for some code sources, and can lead to better parsing accuracy.}
351
352 \begin{apient}
353 virtual Address baseAddress()
354 virtual Address loadAddress()
355 \end{apient}
356 \apidesc{If the binary file type supplies non-zero base or load addresses (e.g. Windows PE), implementations should override these functions.}
357
358 \begin{apient}
359 std::map< Address, std::string > & linkage()
360 \end{apient}
361 \apidesc{Returns a reference to the external linkage map, which may or may not be filled in for a particular CodeSource implementation.}
362
363 \begin{apient}
364 std::vector<CodeRegion *> const& regions()
365 \end{apient}
366 \apidesc{Returns a read-only vector of code regions within the binary represented by this code source.}
367
368 \begin{apient}
369 int findRegions(Address addr, set<CodeRegion *> & ret)
370 \end{apient}
371 \apidesc{Finds all CodeRegion objects that overlap the provided address. Some code sources (e.g. archive files) may have several regions with overlapping address ranges; others (e.g. ELF binaries) do not.}
372
373 \begin{apient}
374 bool regionsOverlap() 
375 \end{apient}
376 \apidesc{Indicates whether the CodeSource contains overlapping regions.}
377
378 \subsection{Class CodeRegion}
379
380 \definedin{CodeSource.h}
381
382 The CodeRegion interface is an accounting structure used to divide CodeSources into distinct regions. This interface is mostly of interest to CodeSource implementors.
383
384 \begin{apient}
385 void names(Address addr, vector<std::string> & names)
386 \end{apient}
387 \apidesc{Fills the provided vector with any names associated with the function at a given address in the region, e.g. symbol names in an ELF or PE binary.}
388
389 \begin{apient}
390 virtual bool findCatchBlock(Address addr, Address & catchStart)
391 \end{apient}
392 \apidesc{Finds the exception handler associated with an address, if one exists. This routine is only implemented for binary code sources that support structured exception handling, such as the SymtabAPI-based SymtabCodeSource provided as part of the ParseAPI.}
393
394 \begin{apient}
395 Address low()
396 \end{apient}
397 \apidesc{The lower bound of the interval of address space covered by this region.}
398
399 \begin{apient}
400 Address high()
401 \end{apient}
402 \apidesc{The upper bound of the interval of address space covered by this region.}
403
404 \begin{apient}
405 bool contains(Address addr)
406 \end{apient}
407 \apidesc{Returns {\scshape true} if $\texttt{addr} \in [\texttt{low()},\texttt{high()})$, {\scshape false} otherwise.}
408
409 \subsection{Class Function}
410
411 \definedin{CFG.h}
412
413 The Function class represents the protion of the program CFG that is reachable through intraprocedural control flow transfers from the function's entry block. Functions in the ParseAPI have only a single entry point; multiple-entry functions such as those found in Fortran programs are represented as several functions that ``share'' a subset of the CFG. 
414
415 \begin{center}
416 \begin{tabular}{ll}
417 \toprule
418 FuncSource & Meaning \\
419 \midrule
420 RT & recursive traversal (default) \\
421 HINT & specified in CodeSource hints \\
422 GAP & speculative parsing heuristics \\
423 GAPRT & recursive traversal from speculative parse \\
424 ONDEMAND & dynamically discovered at runtime \\
425 \bottomrule
426 \end{tabular}
427 \end{center}
428
429 \apidesc{Return type of function \texttt{src()} see description below.}
430
431 \begin{center}
432 \begin{tabular}{ll}
433 \toprule
434 FuncReturnStatus & Meaning \\
435 \midrule
436 UNSET & unparsed function (default) \\
437 NORETURN & will not return \\
438 UNKNOWN & cannot be determined statically \\
439 RETURN & may return \\
440 \bottomrule
441 \end{tabular}
442 \end{center}
443
444 \apidesc{Return type of function \texttt{retstatus()}, see description below.}
445
446 \begin{apient}
447 typedef ContainerWrapper<vector<Block*>,Block*,Block*> blocklist
448 typedef ContainerWrapper<vector<Edge*>,Edge*,Edge*> edgelist
449 \end{apient}
450 \apidesc{Containers for block and edge access. Refer to Section \ref{sec:containers} for details on \texttt{ContainerWrapper}. Library users \emph{must not} rely on the underlying container type of ContainerWrapper lists, as it is subject to change.}
451
452 \begin{apient}
453 const string & name()
454 \end{apient}
455 \apidesc{Returns the name of this function.}
456
457 \begin{apient}
458 CodeRegion * region()
459 \end{apient}
460 \apidesc{Returns the CodeRegion that contains this function's entry point (functions can span multiple regions).}
461
462 \begin{apient}
463 InstructionSource * isrc()
464 \end{apient}
465 \apidesc{Returns the InstructionSource for this function.}
466
467 \begin{apient}
468 CodeObject * obj()
469 \end{apient}
470 \apidesc{Returns the CodeObject containing this function.}
471
472 \begin{apient}
473 FuncSource src()
474 \end{apient}
475 \apidesc{Returns the type of hint that identified this function's entry point.}
476
477 \begin{apient}
478 FuncReturnStatus retstatus()
479 \end{apient}
480 \apidesc{Returns the best-effort determination of whether this function may return or not. Return status cannot always be statically determined, and at most can guarantee that a function \emph{may} return, not that it \emph{will} return.}
481
482 \begin{apient}
483 Block * entry()
484 \end{apient}
485 \apidesc{Returns the basic block at this function's entry point.}
486
487 \begin{apient}
488 bool parsed()
489 \end{apient}
490 \apidesc{Indicates whether this function has been parsed.}
491
492 \begin{apient}
493 blocklist & blocks()
494 \end{apient}
495 \apidesc{Returns a list of the basic blocks comprised by this function. The blocks are guaranteed to be sorted by starting address.}
496
497 \begin{apient}
498 bool contains(Block *b)
499 \end{apient}
500 \apidesc{Returns {\scshape true} if the block is contained in this function.}
501
502 \begin{apient}
503 edgelist & callEdges()
504 \end{apient}
505 \apidesc{Returns a list of all outgoing call edges from this function.}
506
507 \begin{apient}
508 blocklist & returnBlocks()
509 \end{apient}
510 \apidesc{Returns a list of all blocks ending in a \texttt{return} instruction.}
511
512 \begin{apient}
513 std::vector<FuncExtent *> const& extents()
514 \end{apient}
515 \apidesc{Returns a list of contiguous extents of binary code within the function.}
516
517 [The following methods provide additional details about functions to support instrumentation applications and are probably of no interest to most users.]
518
519 \begin{apient}
520 bool hasNoStackFrame()
521 \end{apient}
522 \apidesc{Indicates whether the function sets up a stack frame.}
523
524 \begin{apient}
525 bool savesFramePointer()
526 \end{apient}
527 \apidesc{Indicates whether the function saves a stack frame pointer.}
528
529 \begin{apient}
530 bool cleansOwnStack()
531 \end{apient}
532 \apidesc{Indicates whether the function tears down its own stack on return.}
533
534 \subsection{Class FuncExtent}
535
536 \definedin{CFG.h}
537
538 Function Extents are used internally for accounting and lookup purposes. They may be useful for users who wish to precisely identify the ranges of the address space spanned by functions (functions are often discontiguous, particularly on architectures with variable length instruction sets).
539
540 \begin{apient}
541 Address start()
542 \end{apient}
543 \apidesc{The start of this contiguous code extent.}
544
545 \begin{apient}
546 Address end()
547 \end{apient}
548 \apidesc{The end of this contiguous code extent (exclusive).}
549
550 \subsection{Class Block}
551
552 \definedin{CFG.h}
553
554 A Block represents a basic block as defined in Section \ref{sec:abstractions}, and is the lowest level representation of code in the CFG.
555
556 \begin{apient}
557 typedef ContainerWrapper<vector<Edge*>,Edge*,Edge*> edgelist
558 \end{apient}
559 \apidesc{Container for edge access. Refer to Section \ref{sec:containers} for details. Library users \emph{must not} rely on the underlying container type of ContainerWrapper lists, as it is subject to change.}
560
561
562 \begin{apient}
563 Address start()
564 \end{apient}
565 \apidesc{Returns the lower bound of this block (the address of the first instruction).}
566
567 \begin{apient}
568 Address end()
569 \end{apient}
570 \apidesc{Returns the upper bound (open) of this block (the address immediately
571 following the last byte in the last instruction). }
572
573 \begin{apient}
574 Address lastInsnAddr()
575 \end{apient}
576 \apidesc{Returns the address of the last instruction in this block.}
577
578 \begin{apient}
579 Address size()
580 \end{apient}
581 \apidesc{Returns $\texttt{end()} - \texttt{start()}$.}
582
583 \begin{apient}
584 bool parsed()
585 \end{apient}
586 \apidesc{Indicates whether this block has been parsed.}
587
588 \begin{apient}
589 CodeObject * obj()
590 \end{apient}
591 \apidesc{Returns the CodeObject containing this block.}
592
593 \begin{apient}
594 CodeRegion * region()
595 \end{apient}
596 \apidesc{Returns the CodeRegion containing this block.}
597
598 \begin{apient}
599 edgelist & sources()
600 \end{apient}
601 \apidesc{Return a list of all incomming edges to the block.}
602
603 \begin{apient}
604 edgelist & targets()
605 \end{apient}
606 \apidesc{Return a list of all outgoing edges from the block.}
607
608 \begin{apient}
609 bool consistent(Address addr, Address & prev_insn)
610 \end{apient}
611 \apidesc{Check whether address \texttt{addr} is \emph{consistent} with this basic block. An address is consistent if it is the boundary between two instructions in the block. As long as \texttt{addr} is within the range of the block, \texttt{prev\_insn} will contain the address of the previous instruction boundary before \texttt{addr}, regardless of whether \texttt{addr} is consistent or not.}
612
613 \begin{apient}
614 int containingFuncs()
615 \end{apient}
616 \apidesc{Returns the number of functions that contain this block.}
617
618 \begin{apient}
619 void getFuncs(std::vector<Function *> & funcs)
620 \end{apient}
621 \apidesc{Fills in the provided vector with all functions that share this basic block.}
622
623 \subsection{Class Edge}
624
625 \definedin{CFG.h}
626
627 Typed Edges join two blocks in the CFG, indicating the type of control flow
628 transfer instruction that joins the blocks to each other. Edges may not correspond
629 to a control flow transfer instruction at all, as in the case of the {\scshape
630 fallthrough} edge that indicates where straight-line control flow is split by
631 incoming transfers from another location, such as a branch. While not all
632 blocks end in a control transfer instruction, all control transfer instructions
633 end basic blocks and have outgoing edges; in the case of unresolvable control
634 flow, the edge will target a special ``sink'' block (see \texttt{sinkEdge()},
635 below.
636
637 \begin{center}
638 \begin{tabular}{ll}
639 \toprule
640 EdgeTypeEnum & Meaning \\
641 \midrule
642 CALL & call edge \\
643 COND\_TAKEN & conditional branch--taken \\
644 COND\_NOT\_TAKEN & conditional branch--not taken \\
645 INDIRECT & branch indirect \\
646 DIRECT & branch direct \\
647 FALLTHROUGH & direct fallthrough (no branch) \\
648 CATCH & exception handler \\
649 CALL\_FT & post-call fallthrough \\
650 RET & return \\
651 \bottomrule
652 \end{tabular}
653 \end{center}
654
655 \begin{apient}
656 Block * src()
657 \end{apient}
658 \apidesc{Returns the source block of this edge.}
659
660 \begin{apient}
661 Block * trg()
662 \end{apient}
663 \apidesc{Returns the target block of this edge.}
664
665 \begin{apient}
666 EdgeTypeEnum type()
667 \end{apient}
668 \apidesc{Returns the edge type.}
669
670 \begin{apient}
671 bool sinkEdge()
672 \end{apient}
673 \apidesc{Indicates whether this edge targets the special \emph{sink} block.}
674
675 \begin{apient}
676 bool interproc()
677 \end{apient}
678 \apidesc{Returns {\scshape true} if the edge should be interpreted as interprocedural (e.g. calls, returns, direct branches under certain circumstances).}
679
680 \subsection{Class EdgePredicate}
681 \label{sec:pred}
682
683 \definedin{CFG.h}
684
685 Edge predicates control iteration over edges. For example, the provided
686 \texttt{Intraproc} edge predicate can be passed to an edge iterator
687 constructor, ensuring that only intraprocedural edges are visited during
688 iteration. Two other implementations of EdgePredicate are provided: 
689 \texttt{SingleContext} only visits edges that stay in a single
690 function context, and \texttt{NoSinkPredicate} does not visit edges to 
691 the \emph{sink} block.  The following code traverses 
692 all of the basic blocks within a
693 function:
694
695 \lstset{language=[GNU]C++,basicstyle=\fontfamily{fvm}\selectfont\small}
696 \lstset{numbers=left, numberstyle=\tiny, stepnumber=5, numbersep=5pt}
697 \begin{lstlisting}
698     vector<Block*> work;
699     std::map<Block*,bool> seen; // avoid loops
700     Intraproc epred; // ignore calls, returns
701    
702     work.push_back(func->entry()); // assuming `func' is a Function*
703     seen[func->entry()] = true;
704     while(!work.empty()) {
705         Block * b = work.back();
706         work.pop_back();
707
708         // do some stuff with b...
709    
710         Block::edgelist & targets = block->targets();
711         Block::edgelist::iterator eit = targets.begin(&epred);
712         for( ; eit != targets.end(); ++eit) {
713             Edge * e = (*eit);
714             if(seen.find(e->trg()) == seen.end())
715                 work.push_back(e->trg());
716         }
717     } 
718 \end{lstlisting}
719
720 New edge predicates can be created by implementing the following simple interface:
721
722 \begin{apient}
723 EdgePredicate()
724 EdgePredicate(EdgePredicate * next)
725 \end{apient}
726 \apidesc{Constructs a predicate, either with or without a previously existing predicate to chain it to. Chained predicates return the logical AND over all predicates in the chain.}
727
728 \begin{apient}
729 virtual bool pred_impl(Edge *)
730 \end{apient}
731 \apidesc{Evaluates the predicate on the provided edge.}
732
733 \subsection{Class ParseCallback}
734
735 \definedin{ParseCallback.h}
736
737 The ParseCallback class allows ParseAPI users to be notified of various events
738 during parsing. For most users this notification is unnecessary, and an
739 instantiation of the default ParseCallback can be passed to the CodeObject during initialization. Users who wish to be notified must implement a class that inherits from ParseCallback, and implement one or more of the methods described below to receive notification of those events.
740
741 \begin{apient}
742 struct default_details {
743     default_details(unsigned char*b,size_t s, bool ib) : ibuf(b), isize(s), isbranch(ib) { }
744     unsigned char * ibuf;
745     size_t isize;
746     bool isbranch;
747 }
748 \end{apient}
749 \apidesc{Details used in the \texttt{unresolved\_cf} and \texttt{abruptEnd\_cf}
750 callbacks.}
751
752 \begin{apient}
753 virtual void instruction_cb(Function*,Address,insn_details*)
754 \end{apient}
755 \apidesc{Invoked for each instruction decoded during parsing. Implementing this callback may incur significant overhead.}
756
757 \begin{apient}
758 struct insn_details {
759     InsnAdapter::InstructionAdapter * insn;
760 }
761 \end{apient}
762
763 \begin{apient}
764 void interproc_cf(Function*,Address,interproc_details*)
765 \end{apient}
766 \apidesc{Invoked for each interprocedural control flow instruction.}
767
768 \begin{apient}  
769 struct interproc_details {
770     typedef enum {
771         ret,
772         call,
773         branch_interproc, // tail calls, branches to plts
774         syscall
775     } type_t;
776     unsigned char * ibuf;
777     size_t isize;
778     type_t type;
779     union {
780         struct {
781             Address target;
782             bool absolute_address;
783             bool dynamic_call;
784         } call;
785     } data;
786 }
787 \end{apient}
788 \apidesc{Details used in the \texttt{interproc\_cf} callback.}
789
790 \begin{apient}
791 void overlapping_blocks(Block*,Block*)
792 \end{apient}
793 \apidesc{Noification of inconsistent parse data (overlapping blocks).}
794
795 \subsection{Containers}
796 \label{sec:containers}
797
798 Several of the ParseAPI data structures export containers of CFG objects; the
799 CodeObject provides a list of functions in the binary, for example, while
800 functions provide lists of blocks and so on. To avoid tying the internal
801 storage for these structures to any particular container type, ParseAPI objects
802 export a ContainerWrapper that provides an iterator interface to the internal
803 containers. These wrappers and predicate interfaces are designed to add minimal
804 overhead while protecting ParseAPI users from exposure to internal container
805 storage details. Users \emph{must not} rely on properties of the underlying
806 container type (e.g. storage order) unless that property is explicity stated in
807 this manual.
808
809 \noindent
810 ContainerWrapper containers export the following interface (\texttt{iterator} types vary depending on the template parameters of the ContainerWrapper, but are always instantiations of the PredicateIterator described below):
811
812 \begin{apient}
813 iterator begin()
814 iterator begin(predicate *)
815 \end{apient}
816 \apidesc{Return an iterator pointing to the beginning of the container, with or without a filtering predicate implementation (see Section \ref{sec:pred} for details on filter predicates).}
817
818 \begin{apient}
819 iterator const& end()
820 \end{apient}
821 \apidesc{Return the iterator pointing to the end of the container (past the last element).}
822
823 \begin{apient}
824 size_t size()
825 \end{apient}
826 \apidesc{Returns the number of elements in the container. Execution cost may vary depending on the underlying container type.}
827
828 \begin{apient}
829 bool empty()
830 \end{apient}
831 \apidesc{Indicates whether the container is empty or not.}
832
833 \noindent
834 The elements in ParseAPI containers can be accessed by iteration using an instantiation of the PredicateIterator. These iterators can optionally act as filters, evaluating a boolean predicate for each element and only returning those elements for which the predicate returns {\scshape true}. \emph{Iterators with non-{\scshape null} predicates may return fewer elements during iteration than their \texttt{size()} method indicates.} Currently PredicateIterators only support forward iteration. The operators \texttt{++} (prefix and postfix), \texttt{==}, \texttt{!=}, and \texttt{*} (dereference) are supported.
835
836
837 \appendix
838 \section{Extending ParseAPI}
839 \label{sec:extend}
840
841 The ParseAPI is design to be a low level toolkit for binary analysis tools.
842 Users can extend the ParseAPI in two ways: by extending the control flow
843 structures (Functions, Blocks, and Edges) to incorporate additional data to
844 support various analysis applications, and by adding additional binary code
845 sources that are unsupported by the default SymtabAPI-based code source. For
846 example, a code source that represents a program image in memory could be
847 implemented by fulfilling the CodeSource and InstructionSource interfaces
848 described in Section \ref{sec:codesource} and below. Implementations that
849 extend the CFG structures need only provide a custom allocation factory in
850 order for these objects to be allocated during parsing.
851
852 \subsection{Instruction and Code Sources}
853
854 A CodeSource, as described above, exports its own and the InstructionSource interface for access to binary code and other details. In addition to implementing the virtual methods in the CodeSource base class (Section \ref{sec:codesource}), the methods in the pure-virtual InstructionSource class must be implemented:
855
856 \begin{apient}
857 virtual bool isValidAddress(const Address) 
858 \end{apient}
859 \apidesc{Returns {\scshape true} if the address is a valid code location.}
860
861 \begin{apient}
862 virtual void* getPtrToInstruction(const Address)
863 \end{apient}
864 \apidesc{Returns pointer to raw memory in the binary at the provided address.}
865
866 \begin{apient}
867 virtual void* getPtrToData(const Address)
868 \end{apient}
869 \apidesc{Returns pointer to raw memory in the binary at the provided address. The address need not correspond to an executable code region.}
870
871 \begin{apient}
872 virtual unsigned int getAddressWidth()
873 \end{apient}
874 \apidesc{Returns the address width (e.g. four or eight bytes) for the represented binary.}
875
876 \begin{apient}
877 virtual bool isCode(const Address)
878 \end{apient}
879 \apidesc{Indicates whether the location is in a code region.}
880
881 \begin{apient}
882 virtual bool isData(const Address)
883 \end{apient}
884 \apidesc{Indicates whether the location is in a data region.}
885
886 \begin{apient}
887 virtual Address offset()
888 \end{apient}
889 \apidesc{The start of the region covered by this instruction source.}
890
891 \begin{apient}
892 virtual Address length()
893 \end{apient}
894 \apidesc{The size of the region.}
895
896 \begin{apient}
897 virtual Architecture getArch()
898 \end{apient}
899 \apidesc{The architecture of the instruction source. See the Dyninst manual for details on architecture differences.}
900
901 \begin{apient}
902 virtual bool isAligned(const Address)
903 \end{apient}
904 \apidesc{For fixed-width instruction architectures, must return {\scshape true} if the address is a valid instruction boundary and {\scshape false} otherwise; otherwise returns {\scshape true}. This method has a default implementation that should be sufficient.}
905
906 CodeSource implementors need to fill in several data structures in the base CodeSource class:
907
908 \begin{apient}
909 std::map<Address, std::string> _linkage
910 \end{apient}
911 \apidesc{Entries in the linkage map represent external linkage, e.g. the PLT in ELF binaries. Filling in this map is optional.}
912
913 \begin{apient}
914 Address _table_of_contents
915 \end{apient}
916 \apidesc{Many binary format have ``table of contents'' structures for position
917 independant references. If such a structure exists, its address should be filled in.}
918
919 \begin{apient}
920 std::vector<CodeRegion *> _regions
921 Dyninst::IBSTree<CodeRegion> _region_tree
922 \end{apient}
923 \apidesc{One or more contiguous regions of code or data in the binary object must be registered with the base class. Keeping these structures in sync is the responsibility of the implementing class.}
924
925 \begin{apient}
926 std::vector<Hint> _hints
927 \end{apient}
928 \apidesc{CodeSource implementors can supply a set of Hint objects describing where functions are known to start in the binary. These hints are used to seed the parsing algorithm. Refer to the CodeSource header file for implementation details.}
929
930 \subsection{CFG Object Factories}
931 \label{sec:factories}
932
933 Users who which to incorporate the ParseAPI into large projects may need to store additional information about CFG objects like Functions, Blocks, and Edges. The simplest way to associate the ParseAPI-level CFG representation with higher-level implementation is to extend the CFG classes provided as part of the ParseAPI. Because the parser itself does not know how to construct such extended types, implementors must provide an implementation of the CFGFactory that is specialized for their CFG classes. The CFGFactory exports the following simple interface:
934
935 \begin{apient}
936 virtual Function * mkfunc(Address addr, 
937     FuncSource src,
938     std::string name, 
939     CodeObject * obj, 
940     CodeRegion * region,
941     Dyninst::InstructionSource * isrc)
942 \end{apient}
943 \apidesc{Returns an object derived from Function as though the provided parameters had been passed to the Function constructor. The ParseAPI parser will never invoke \texttt{mkfunc()} twice with identical \texttt{addr}, and \texttt{region} parameters---that is, Functions are guaranteed to be unique by address within a region.}
944
945 \begin{apient}
946 virtual Block * mkblock(Function * func, CodeRegion * region, Address addr)
947 \end{apient}
948 \apidesc{Returns an object derived from Block as though the provided parameters had been passed to the Block constructor. The parser will never invoke \texttt{mkblock()} with identical \texttt{addr} and \texttt{region} parameters.}
949
950 \begin{apient}
951 virtual Edge * mkedge(Block * src, Block * trg, EdgeTypeEnum type)
952 \end{apient}
953 \apidesc{Returns an object derived from Edge as though the provided parameters had been passed to the Edge constructor. The parser \emph{may} invoke \texttt{mkedge()} multiple times with identical parameters.}
954
955 \begin{apient}
956 virtual Block * mksink(CodeObject *obj, CodeRegion *r)
957 \end{apient}
958 \apidesc{Returns a ``sink'' block derived from Block to which all unresolvable control flow instructions will be linked. Implementors may return a unique sink block per CodeObject or a single global sink.}
959
960 Implementors of extended CFG classes are required to override the default implementations of the \emph{mk*} functions to allocate and return the appropriate derived types statically cast to the base type. Implementors must also add all allocated objects to the following internal lists:
961
962 \begin{apient}
963 fact_list<Edge> edges_
964 fact_list<Block> blocks_
965 fact_list<Function> funcs_
966 \end{apient}
967 \apidesc{O(1) allocation lists for CFG types. See the CFG.h header file for list insertion and removal operations.}
968
969 Implementors \emph{may} but are \emph{not required to} override the
970 deallocation following deallocation routines. The primary reason to override
971 these routines is if additional action or cleanup is necessary upon CFG object
972 release; the default routines simply remove the objects from the allocation
973 list and invoke their destructors.
974
975 \begin{apient}
976 virtual void free_func(Function * f)
977 virtual void free_block(Block * b)
978 virtual void free_edge(Edge * e)
979 virtual void free_all()
980 \end{apient}
981 \apidesc{CFG objects should be freed using these functions, rather than delete, to avoid leaking memory.}
982
983 \section{Defensive Mode Parsing}
984 \label{sec:defmode}
985
986 Binary code that defends itself against analysis may violate the
987 assumptions made by the the ParseAPI's standard parsing algorithm.
988 Enabling defensive mode parsing activates more conservative
989 assumptions that substantially reduce the percentage of code that is
990 analyzed by the ParseAPI.  For this reason, defensive mode parsing is
991 best-suited for use of ParseAPI in conjunction with dynamic analysis
992 techniques that can compensate for its limited coverage of the binary
993 code.  This mode of parsing will be brought to full functionality in 
994 an upcoming release.  
995
996 \end{document}