Method compute_density

src/analysis/adg.rs:264–295

(&self)

    }

    pub fn compute_density(&self) -> usize {
        let mut undigraph: Graph<Node, (), Undirected> = Graph::default();
        for node in self.graph.node_indices() {
            undigraph.add_node(self.graph[node].clone());
        }

        for edge in self.graph.edge_references() {
            let (a, b) = (edge.source(), edge.target());
            if !undigraph.contains_edge(a, b) && !undigraph.contains_edge(b, a) {
                undigraph.add_edge(a, b, ());
            }
        }
        let scc = petgraph::algo::kosaraju_scc(&undigraph);
        // compute the number of nodes in the largest connected component.
        let density = scc
            .iter()
            .map(|subgraph| {
                let mut api_calls = Vec::new();
                // count number of api calls in each subgraph
                for node in subgraph {
                    let node_weight = undigraph.node_weight(*node).unwrap();
                    let node_name = node_weight.get_name();
                    if get_func_gadget(&node_name).is_some() {
                        api_calls.push(node);
                    }
                }
                api_calls.len()
            })
            .max()
            .unwrap_or(1);
        density
    }
}

/// Taint structure attached with each symbol.