  A modern binary executable is a composition of various networks. Control flow
graphs are commonly used to represent an executable program in labeled datasets
used for classification tasks. Control flow and term representations are widely
adopted, but provide only a partial view of program semantics. This study is an
empirical analysis of the networks composing malicious binaries in order to
provide a complete representation of the structural properties of a program.
This is accomplished by the measurement of structural properties of program
networks in a malicious binary executable dataset. We demonstrate the presence
of Scale-Free properties of network structure for program data dependency and
control flow graphs, and show that data dependency graphs also have Small-World
structural properties. We show that program data dependency graphs have a
degree correlation that is structurally disassortative, and that control flow
graphs have a neutral degree assortativity, indicating the use of random graphs
to model the structural properties of program control flow graphs would show
increased accuracy. By providing an increase in feature resolution within
labeled datasets of executable programs we provide a quantitative basis to
interpret the results of classifiers trained on CFG graph features. An increase
in feature resolution allows for the structural properties of program classes
to be analyzed for patterns as well as their component parts. By capturing a
complete picture of program graphs we can enable theoretical solutions for the
mapping a program's operational semantics to its structure.
