Computes cyclomatic complexity of all functions in a binary Raw

cyclomatic.ml

open Core_kernel.Std
open Bap.Std
open Graphlib.Std

module G = Graphs.Cfg

let complexity graph =
  let edges = Seq.length (G.edges graph) in
  let nodes = Seq.length (G.nodes graph) in
  let parts = Graphlib.strong_components (module G) graph |>
              Partition.number_of_groups in
  edges - nodes + parts

let connect_graph g entry =
  G.nodes g |> Seq.fold ~init:g ~f:(fun g n ->
      if G.Node.degree ~dir:`Out n g = 0
      then G.Edge.insert (G.Edge.create n entry `Jump) g
      else g)


let main proj =
  Project.symbols proj |>
  Symtab.to_sequence |>
  Seq.fold ~init:Int.Map.empty ~f:(fun subs (name,entry,cfg) ->
      let c = complexity (connect_graph cfg entry) in
      Map.add subs ~key:c ~data:name) |>
  Map.iteri ~f:(fun ~key ~data -> printf "%s: %d\n" data key)

let () = Project.register_pass' main