gcc plugin to collect cross-references, part 2

Part 1

Because I still fighting with endless variants of unnamed types while processing linux kernel lets talk about persistence

 

The final goal of this plugin is to make from sources database of functions for methods they call and fields they use. After that you can find set of functions referring to some field/method and investigate them later with disasm for example

 

So sure plugin must store it`s results to somewhere

Probably graph databases is better suited for such data - like you can put symbols as vertices and references as edges, then all references to some symbol is just all of it`s incoming edges. But I am too lazy to install JVM and Neo4j, so I used SQLite (and simple YAML-like files for debugging). You can connect your own storage by implementing interface FPersistence

gcc plugin to collect cross-references, part 1

Every user of IDA Pro likes cross-references - they are very useful but applicable for objects in global memory only. What if I want to have cross-references for virtual methods and class/record fields - like what functions some specific virtual method was called from? Unfortunately IDA Pro cannot shows this - partially because this information is not stored in debug info and also due to weak algo for types propagation. Call of virtual method typically looks similar to

 mov rax, [rbp+var_8] ; this
 mov     rax, [rax]   ; this._vptr
 add     rax, 10h
 mov     rcx, [rax]   ; load method from vtable, why not mov rcx, [rax+0x10]?
 call    rcx ; or even better just call [rax+0x10]?

Lets think where we can get such kind of cross-references - sure compiler must have it somewhere inside to generate native code, right? So generally speaking compiler is your next friend (right after disassembler and debugger).

Run gcc with -c -fdump-final-insns options on simple C++ test file and check how call of virtual method looks like:
(call_insn # 0 0 2 (set (reg:DI 0 ax)
        (call (mem:QI (reg/f:DI 1 dx [orig:85 _4 ] [85]) [ *OBJ_TYPE_REF(_4;this_7(D)->3B) S1 A8])
            (const_int 0 [0]))) "vtest.cc":31:21# {*call_value}

What? What is _4, which type has this and what means ->3B instead of method name? Looking ahead, I can say that actually all needed information really stored in RTL thought function dump_generic_node (from tree-pretty-print.cc) is just too lazy to show it properly. Seems that we can develop gcc plugin to extract this cross-references (in fact, the first couple of months of development this was not at all obvious)

why gcc?

bcs gcc is standard de-facto and you can expect that you will able to build with it almost any sources (usually after numerous loud curses finally read the documentation), even on windows. Nevertheless lets consider other popular alternatives

ctf-like task based on maximal clique problem

Sources

There is undirected graph with 1024 vertices and 100909 edges (so average degree is 98.5). It is known that the graph contains clique with size 16. You can pass indexes of clique`s vertices in command line like

./ctf 171 345

./ctf 171 346
too short clique 

This vertices of clique then used to derive AES key and decrypt some short string

Can you solve this?

yet another maximal clique algorithm

It seems that most of known algorithms for maximal clique try to add as much vertices as possibly and evolving towards more complex heuristics for vertices ordering. But there is opposite way - we can remove some vertices from neighbors, right?

Lets assume that we sorted all vertices of graph with M vertices and N edges by their degrees in descending order and want to check if some vertex with degree K can contain clique. We can check if all of it`s neighbors mutually connected and find one or several most loosely connected vertices - lets name it L. This checking requires K -1 access to adjacency matrix for first vertex, K -2 for second etc - in average (K^ 2) / 2. If no unconnected vertices was found - all survived neighbors are clique. See sample of implementation in function naive_remove

Now we should decay what we can do with L and there is only 2 variants:

1. we can remove it from set of neighbors
2. we can keep it and remove from set of neighbors all vertices not connected with L
   

Notice that in both cases amount of neighbors decreased by at least 1. Now we can recursively repeat this process with removed and remained L at most K times, so complexity will be O = (K ^ 2) / 2 * (2 ^ K)

We can repeat this process for all vertices with degree bigger than maximal size of previously found clique - in worse case M times, so overall complexity of this algorithm is O = M * (K ^ 2) / 2 * (2 ^ K)

In average K =  N / M

well, not very good result but processing of each vertex can be done in parallel

We can share adjacency matrix (or even make it read-only) between all working threads and this recursive function will require in each step following memory:

1. bitset of survived neighbors - K / 8 where V[i] is 1 if this vertex belongs to neighbors and 0 if it was removed
   
2. array for unconnected vertices counts with size K

given that recursion level does not exceed K overall used space on stack is

S = K * (K / 8 + K * sizeof(index))

now check if we can run this algorithm on

gpu

Disclaimer: I read book about CUDA programming almost 10 years ago so I can be wrong

estimation of maximum clique size

definition 1.1 from really cool book "The Design of Approximation Algorithms":

An α-approximation algorithm for an optimization problem is a polynomial-time algorithm that for all instances of the problem produces a solution whose value is within a factor of α of the value of an optimal solution

so you need first to estimate at least size of possible optimal solution, right?

Surprisingly I was unable to find it for maximal clique. stackexchange offers very simple formula (spoiler: the actual size is a couple of orders of magnitude smaller). python networkX offers method with complexity O(1.4422ⁿ) to find maximal clique itself only. cool. Let's invent this algorithm by ourselves

From wikipedia:

A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent

in other words this means that graph with maximal clique of size K should contains at least K vertices with degree K - 1 or bigger. So we can arrange vertices on degrees and find some degree S where amount of vertices with degree S or bigger is >= S. But this is very rough estimation and it could be refined taking into account the following observation - we can remove all edges to vertices not belonging to this subgraph. So algo is:

1. calculate degrees of all vertices and arrange them in descending order
2. for each degree S find first where amount of vertices with degree S or bigger is >= S
3. put all such vertices in sub-graph SD
4. remove from SD all edges to vertices not belonging to SD
5. recalculate degrees of all vertices in SD
6. find another degree S in SD where amount of vertices with degree S or bigger is >= S. this will be result R

next we can repeat steps 2-6 until enumerate all degrees or some degree will be less than the previously found result R

Complexity

Let N - amount of vertices and M - amount of edges. Then cycle can run max N times and in each cycle we can remove less that M edges (actually in average M/2), so in worst case complexity is O(MN/2)

Results 

custom attributes in gcc and dwarf

Lets check if we can add our own attributes (if Google can afford it, then why is it forbidden to mere mortals?). For example I want to have in gcc and dwarf flag about functions/methods parameters direction - is some param IN or OUT. I chose the value of this dwarf attribure 0x28ff

It`s pretty obviously that we can add our own custom attribute in gcc - they even have example how to do this. But what about dwarf producer? Long story short - seems that you cannot do it from plugin. The only dwarf related pass for plugins is pass_dwarf2_frame. So we need to patch gcc. But before this we need to 

build gcc from sources

At moment of writing latest stable version of gcc was 12.0 so run 


git clone --branch releases/gcc-12 https://github.com/gcc-mirror/gcc.git

and then follows instructions

patch gcc

Lets see how gcc produces dwarf output. All symbol table formatters implement gcc_debug_hooks and currently gcc has 3 (btw there are patches for mingw to produce PDB, so in theory you could have vmlinux.pdb):

• dwarf2out.cc - this is our target
• godump.c
• vmsdbgout.c
  

so lets add function add_param_direction in dwarf2out.cc:
bool add_param_direction(tree decl, dw_die_ref parm_die)
{
  bool pa1 = lookup_attribute ("param_in", DECL_ATTRIBUTES (decl));
  bool pa2 = lookup_attribute ("param_out", DECL_ATTRIBUTES (decl));
  if ( !(pa1 ^ pa2) )
    return false;
  unsigned char pa_value = 0;
  // seems that you can`t have flag with value 1 - see gcc_assert at line 9599
  if ( pa1 )
    pa_value = 2;
  if ( pa2 )
    pa_value = 3;
  add_AT_flag(parm_die, (dwarf_attribute)0x28ff, pa_value);
  return true;
}

It first checks if parameter has attribute param_in or param_out (but not both at the same time bcs this is senseless) and adds custom dwarf flag attribute via add_AT_flag call. Then we just need to call this function from gen_formal_parameter_die

 

Now we can add our custom attributes - this can be done via plugin but I preferred to patch c-family/c-attribs.cc:

 

tree handle_param_in_attribute (tree *node, tree name, tree ARG_UNUSED (args),
                         int ARG_UNUSED(flags), bool *no_add_attrs)
{
  if ( !DECL_P (*node) )
  {
    warning (OPT_Wattributes, "%qE attribute can apply to params declarations only", name);
    *no_add_attrs = true;
    return NULL_TREE;
  }
  tree decl = *node;
  if (TREE_CODE (decl) != PARM_DECL)
  {
    warning (OPT_Wattributes, "%qE attribute can apply to params only", name);
    *no_add_attrs = true;
  } else {
    // check presense of param_out
    if ( lookup_attribute ("param_out", DECL_ATTRIBUTES (decl)) )
    {
      warning (OPT_Wattributes, "%qE attribute useless when param_out was used", name);
      *no_add_attrs = true;
      DECL_ATTRIBUTES (decl) = remove_attribute("param_out", DECL_ATTRIBUTES (decl));
    }
  }
  return NULL_TREE;
}


Function handle_param_in_attribute checks that this attribute linked with function/method parameter. Then it checks that the same parameter don`t have attribute param_out - in this case it just removes both

 

All patches located here 

results

custom dwarf attributes in golang

Finally I found them

0x2900

DW_AT_go_kind, form DW_FORM_data1. Internal golang types kind. For example DW_TAG_structure_type can have kind Struct, Slice or String. I made script to extract statistic which kind can be attached to dwarf tags

0x2901

DW_AT_go_key, form DW_FORM_ref_addr - tag ID. Can be attached to kindMap

0x2902

DW_AT_go_elem, form DW_FORM_ref_addr - tag ID. Can be attached to

• kindChan
• kindMap
• kindSlice

0x2903

DW_AT_go_embedded_field, form DW_FORM_flag. If non-zero member is embedded structure

0x2904

DW_AT_go_runtime_type, form DW_FORM_addr. I don`t know what is it - sure this is not real VA bcs it can point to random sections and even be out of elf module

0x2905

DW_AT_go_package_name, form DW_FORM_string. Just package name for compilation unit

0x2906

DW_AT_go_dict_index, form DW_FORM_udata

index of the dictionary entry describing the real type of this type shape