codeql-workshop-dataflow-c/readme-low-level.org

• CodeQL AST in dot and pdf
• CodeQL CFG in dot and pdf
• AST
• CFG
• GPTs
• Render via dot
• AST-CFG HYBRID
• CFG with numbered nodes
• Source Annotated with CFG Nodes

CodeQL AST in dot and pdf

The control flow graph is narrowed to the function of interest,

  int copy_mem(unsigned int unused, dyn_input_t *input,
               unsigned int input_types) {...}

from ./tests-common/test_part1.c, so we do the same for the AST.

  # Produce ast in dot format
  codeql database analyze                             \
         --format=dot --output=ast.dot                \
         -j8 -v --ram=16000                           \
         --rerun                                      \
         --                                           \
         cpp-dataflow-part1-database                  \
         graphs/ast.ql                            

  # Convert dot to pdf
  dot -Tpdf < ast.dot/cpp/print-ast.dot > ast.dot/cpp/print-ast.pdf
  dot -Tsvg < ast.dot/cpp/print-ast.dot > ast.dot/cpp/print-ast.svg

  # View the graph
  open ast.dot/cpp/print-ast.pdf

  # This comes from
  tests-common/test_part1.c

CodeQL CFG in dot and pdf

The whole control flow graph is very large, so the query narrows it to the function of interest,

  int copy_mem(unsigned int unused, dyn_input_t *input,
               unsigned int input_types) {...}

from ./tests-common/test_part1.c

  # Produce CFG in dot format
  codeql database analyze                             \
         --format=dot --output=cfg.dot                \
         -j8 -v --ram=16000                           \
         --rerun                                      \
         --                                           \
         cpp-dataflow-part1-database                  \
         graphs/cfg.ql                            


  # Convert dot to pdf
  dot -Tpdf < cfg.dot/cpp/print-cfg.dot > cfg.dot/cpp/print-cfg.pdf
  dot -Tsvg < cfg.dot/cpp/print-cfg.dot > cfg.dot/cpp/print-cfg.svg

  # View the graph
  open cfg.dot/cpp/print-cfg.pdf

AST

The ast is inlined here. For better viewing, open the pdf (./ast.dot/cpp/print-ast.pdf) separately.

CFG

The cfg is inlined here. For better viewing, open the pdf (./cfg.dot/cpp/print-cfg.pdf) separately.

GPTs

A gpt was used to add 17 of the CFG edges to the AST tree; more resulted in a very confusing graph. The hybrid is in cfg.dot/cpp/ast-cfg-hybrid.dot

Render via dot

The hybrid is rendered via dot. The other renderers produced very spread layouts.

  # Convert dot to pdf
  twopi -Tpdf < cfg.dot/cpp/ast-cfg-hybrid.dot > cfg.dot/cpp/ast-cfg-hybrid.pdf
  circo -Tpdf < cfg.dot/cpp/ast-cfg-hybrid.dot > cfg.dot/cpp/ast-cfg-hybrid.pdf
  dot -Tpdf < cfg.dot/cpp/ast-cfg-hybrid.dot > cfg.dot/cpp/ast-cfg-hybrid.pdf
  dot -Tsvg < cfg.dot/cpp/ast-cfg-hybrid.dot > cfg.dot/cpp/ast-cfg-hybrid.svg

  # View the graph
  open -a skim cfg.dot/cpp/ast-cfg-hybrid.pdf

AST-CFG HYBRID

The ast-cfg hybrid is inlined here. For better viewing, open the pdf (./cfg.dot/cpp/ast-cfg-hybrid.pdf) separately.

CFG with numbered nodes

The CFG with node numbering is inlined here. For better viewing, open the pdf (./cfg.dot/cpp/cfg-annotated.pdf) separately.

As before, this graph is rendered via dot:

  dot -Tpdf < cfg.dot/cpp/cfg-annotated.dot > cfg.dot/cpp/cfg-annotated.pdf
  dot -Tsvg < cfg.dot/cpp/cfg-annotated.dot > cfg.dot/cpp/cfg-annotated.svg

  # View the graph
  open -a skim cfg.dot/cpp/cfg-annotated.pdf

Source Annotated with CFG Nodes

The CFG entries

  0[label="ExprStmt (0)"; ];
  1[label="call to memcpy (1)"; ];
  2[label="input (2)"; ];
  3[label="0 (3)"; ];
  4[label="access to array (4)"; ];
  5[label="ptr (5)"; ];
  6[label="buf (6)"; ];
  7[label="input (7)"; ];
  8[label="1 (8)"; ];
  9[label="access to array (9)"; ];
  10[label="ptr (10)"; ];
  11[label="buf (11)"; ];

are located in the source code as follows

  int    copy_mem(unsigned    int    unused,    dyn_input_t    *input,


                  unsigned    int    input_types)    {
                                                     0

          memcpy(input[0].ptr.buf,    input[1].ptr.buf,
          1      2     3              7     8
                      4   5   6            9   10  11

                 input[1].ptr.size);


      copy_mem_nested(input);

      ...;
  }