adds the stub resolver abi pass #1036

gitoleg · 2020-01-22T18:43:31Z

The stub resolver pass redirects on the IR level calls to stub functions to the calls to real functions if such could be identified. A function is a stub if it has the stub attribute present in the knowledge base. So far, we add only a knowledge provider for ELF stubs (that looks into the .plt section) others will be added later. The redirection algorithm establishes a one-to-one mapping between a stub and its prospective redirection. In case if a non-bijective mapping is detected (a stub has more than one implementation candidates or implementation has more than one stubs) no redirection is established.

The problem arises when we deal with libraries: even if a callee is in the same library, a call will be done through a plt entry first, meaning that we won't visit the target subroutine. Our solution is based on the function name: we would better to call the function itself, but not the corresponding plt entry, so since a function and a plt entry has the same name, then any call to a plt entry we substitute to a call to the function. Also, this PR fixes SP in the `primus-x86-loader` (again). The history. PR BinaryAnalysisPlatform#993 introduced a proper initialization of PLT entries, but unfortunately, introduced a bug as well. Briefly, we didn't want primus to dive deep into PLT entries because anyway, we would fail with unresolved call exception, but to that moment a SP would be changed several times. The solution was to raise an unresolved call exception as soon as possible, right after a primus machine entered an entry and restore SP by `unresolved-call` observation. Unfortunately, the implementation was wrong: we linked an unresolved call handler to the address of a jump in a plt entry, so actually we just call a handler instead, and no actual unresolved call happens, no observation made, and no steps to restore SP taken. This PR fixes it and now we just unlink all the addresses of plt entries, so we get a fair unresolved call exception.

ivg

In general, I like the idea of unlinking PLT and relinking jumps to implementation. I am a little bit concerned that this is not a pass, like trivial-condition-form for example, and I am not quite happy that Primus run modifies the program. So we should consider moving this to a normal pass (in fact the abi pass), as what it does is called relocating a procedure that in general useful not only for Primus.

So, I'm suggesting to split the relocation part into an abi pass.

Concerning the rest of implementation, aka component Component. We will discuss it more in depth on the second round, I have suspicions that your initial problem evaluation has some flaws. I'm currently revisiting the old PRs.

plugins/primus_x86/primus_x86_loader.ml

ivg · 2020-01-24T15:33:33Z

plugins/primus_x86/primus_x86_main.ml

@@ -3,7 +3,8 @@ open Bap_primus.Std
 include Self()

 let init _ =
-  Primus.Machine.add_component (module Primus_x86_loader.Component);;
+  Primus.Machine.add_component (module Primus_x86_loader.Component);


a component named component?

ivg · 2020-01-24T15:41:22Z

Unfortunately, the implementation was wrong: we linked an unresolved call handler to the address of a jump in a plt entry, so actually we
just call a handler instead, and no actual unresolved call happens, no observation made, and no steps to restore SP taken.

That is not true :) Observations had happened by that time, therefore the code was correct. Weneed to reevaluate the problem and confirm that observations indeed do not happen and if they not identify why. My personal bet is that they do happen :)

In BinaryAnalysisPlatform#1051 we begun inserting `start` and `exit` pseudonodes and introduced a small bug, when the graph is singleton and has a node with both indegree and outdegree equal to zero. For that graphs, instead of ``` digraph { start -> n -> exit } ``` we got ``` digraph { start -> n; start -> exit; } ``` since we didn't insert an edge from `n` to `exit`.

…fies-x86-loader

ivg

The algorithm should do the following:
For each call that has a destination that is a stub, s.t. there is a function that is not a stub that we can unambiguously link with that stub, relink the destination to that function.
Keep in mind, that for each stub there should be at most one function that matches this stub. And for each non-stub there should be at most one stub that matches this function. In case of any ambiguity, i..e, a function that can satisfy more than one stubs should be removed from the linking process, the same a stub that satisfy more than one functions, shouldn't be relinked.

write knowledge providers that will provide the stub attribute for known to you stubs.

plugins/stub_resolver/stub_resolver_main.ml

…fies-x86-loader

plugins/primus_x86/primus_x86_loader.ml

ivg

Please address the issues that will be relevant after you will rewrite this to enable the announced property that the rewriting preserves one-to-one correspondence between stubs and implementation:

In case if a non-bijective mapping is detected (a stub has more than one implementation candidates or implementation has more than one stubs) no redirection is established.

For that, implement the relinker using the unification algorithm: start by partitioning the set of program subroutines by the equivalence relation E in which two functions are equivalent if they share the same alias. Then refine this quotient set by removing all sets that do not have exactly two elements. Finally, leave only those pairs in which one and only one element is a stub. Those pairs will give the most general unifier.

ivg · 2020-04-13T17:37:52Z

plugins/stub_resolver/stub_resolver_main.ml

+let update prog = relink prog (find_links prog)
+
+let main proj =
+  Plt.provide proj;


this should be removed from the abi pass. In other words, move this line to line 148.

ivg · 2020-04-13T18:38:34Z

plugins/stub_resolver/stub_resolver_main.ml

+open KB.Syntax
+
+type t = {
+  aliases : tid option String.Map.t;


type binding = Unique of tid | Ambiguous instead of tid option so that at the end you will have a tri-state binding - either None, Some (Unique x), or Some Ambiguous .

Maps with 'a option as a value is very confusing, as you have the None constructor overloaded to have two completely different meanings. And that in Some None, None meanys too many. Something is wrong in representing "too many" with None.

ivg · 2020-04-13T18:50:38Z

plugins/stub_resolver/stub_resolver_main.ml

+open KB.Syntax
+
+type t = {
+  aliases : tid option String.Map.t;


also, rename aliases to stubs and symbols to reals or impls to reflect the actual meaning of both fields.

ivg · 2020-04-14T00:31:30Z

plugins/stub_resolver/stub_resolver_main.ml

+        | Second _ -> jmp
+        | First tid -> match Map.find links tid with
+          | Some (Some tid') ->
+            Jmp.reify


don't create a new jmp term as we will lose as a result al the attributes of the old term. Map the old term using the with_alt function. That is not exposed in the interface, so please expose it also (together with the with_dst function).

ivg · 2020-04-14T12:44:48Z

Also, please add unit tests and function tests (with a .so that has functions with external and static linkage calling each other).

Also, make sure that examples from draperlaboratory/cbat_tools#132 are linked correctly.

…fies-x86-loader

ivg · 2020-04-16T18:30:18Z

lib/bap/bap.mli

+
+    (** [with_dst jmp d] updates jump's intra-procedural destination  *)
+    val with_dst : t -> dst option -> t
+


could you also add @since attributes? since 2.0.0 for with_{kind,cond} and 2.10 for the latter two.

ivg · 2020-04-16T18:32:35Z

plugins/api/api/c/gnu.h

@@ -1 +1,3 @@
 int __libc_start_main(int (*main) (int, char **, char **), int, char **, void *auxv);
+
+void __stack_chk_fail(void)  __attribute__((noreturn));


why is it here?

ivg · 2020-04-16T18:33:17Z

plugins/stub_resolver/run_stub_resolver_tests.ml

+    Stub_resolver_tests.suite;
+  ]
+
+let load_plugins () =


delete this

ivg · 2020-04-16T18:51:24Z

plugins/stub_resolver/stub_resolver.ml

+type t = {
+  groups : groups;
+  names  : names;
+  next   : int;


As a side note, a trick that I usually employ is that instead of maintaining the counter, we can use Map.max_elt instead of next. But you can keep next if you like.

ivg · 2020-04-16T19:10:00Z

plugins/stub_resolver/stub_resolver_tests.ml

+      ]
+      ~expected:["siera",   "papa";
+                 "tango",   "quebec";
+                 "uniform", "romeo";];


We need cases where symbols have many aliases, some intersecting aliases and some not, but where there is more than two cases, e.g.,

test "several intersections" [ stub, "a", ["a1"; "a2"; "a3"]; real, "a0", ["a"]; stub, "b", ["b1"; "b2"; "b3"]; real, "b0", ["b"; "c"]; real, "c", ["d"]; stub, "d", []; ] ~expect:[ "a", "a0"; ]

and more tests like this.

plugins/stub_resolver/stub_resolver_tests.ml

ivg · 2020-04-17T16:27:00Z

Ok, it's good to go. Merge as soon as Travis greenlights!

ivg · 2020-06-10T14:32:36Z

plugins/stub_resolver/stub_resolver_main.ml

+|}
+
+let () = Extension.declare @@ fun _ctxt ->
+  Stream.observe Project.Info.data @@ Plt.provide;


Why is it Project.Info.data not Project.Info.code? The .plt entries are in the code segment and are executable, so marking something in the data section as valid code seems quite wrong.

@gitoleg, any comments?

ivg requested changes Jan 24, 2020

View reviewed changes

gitoleg added 2 commits January 29, 2020 15:09

Merge remote-tracking branch 'upstream/master' into rectifies-x86-loader

9ad34dc

refactoring

8baae4e

gitoleg added the ready for review label Jan 30, 2020

gitoleg requested a review from ivg January 30, 2020 16:55

ivg removed the ready for review label Feb 6, 2020

gitoleg added 5 commits February 6, 2020 14:34

moved abi pass to a plugin. wip

0d5d8f3

updated docs

8daf889

wip

2b1d82e

merge with master

5c7112e

rolled back unintended changes

4824890

gitoleg force-pushed the rectifies-x86-loader branch from b5c5121 to 4824890 Compare February 13, 2020 00:30

ivg and others added 3 commits February 19, 2020 12:56

merge with master

6d7971a

Merge remote-tracking branch 'origin/rectifies-x86-loader' into recti…

00eb99b

…fies-x86-loader

ivg requested changes Feb 26, 2020

View reviewed changes

gitoleg added 8 commits February 26, 2020 13:40

Merge remote-tracking branch 'upstream/master' into rectifies-x86-loader

8b7c22b

reimplemented

b8344ce

Merge remote-tracking branch 'upstream/master'

1ee5a2c

Merge remote-tracking branch 'upstream/master'

8b5710e

Merge remote-tracking branch 'upstream/master'

704b018

Merge branch 'master' into rectifies-x86-loader

318509f

Merge remote-tracking branch 'origin/rectifies-x86-loader' into recti…

75daa1a

…fies-x86-loader

refactored a little

84e74db

gitoleg requested a review from ivg March 16, 2020 00:10

ivg mentioned this pull request Apr 13, 2020

Add spec for inlining plt entries draperlaboratory/cbat_tools#134

Closed

ivg requested changes Apr 13, 2020

View reviewed changes

plugins/primus_x86/primus_x86_loader.ml Outdated Show resolved Hide resolved

Merge remote-tracking branch 'upstream/master' into rectifies-x86-loader

2b8755d

rolls back primus x86 loader

6e2d94b

gitoleg changed the title ~~rectifies x86 primus loader~~ adds the stub resolver abi pass Apr 13, 2020

rolls back primus x86 loader

896803b

ivg requested changes Apr 14, 2020

View reviewed changes

gitoleg added 5 commits April 15, 2020 14:23

wip

880ae67

wrote unit tests, refactoring

3ce0056

Merge remote-tracking branch 'origin/rectifies-x86-loader' into recti…

6b951ba

…fies-x86-loader

rewrote oasis file

91395ef

adds stub resolver tests on travis

0eb1081

ivg requested changes Apr 16, 2020

View reviewed changes

gitoleg added 3 commits April 17, 2020 12:03

now we mangle new subroutines

6742437

updated testsuite, a couple new unit tests

da31f61

just a tiny stylistic update

e6edeb6

ivg approved these changes Apr 17, 2020

View reviewed changes

gitoleg merged commit a11d6b7 into BinaryAnalysisPlatform:master Apr 17, 2020

gitoleg deleted the rectifies-x86-loader branch May 13, 2020 21:08

ivg reviewed Jun 10, 2020

View reviewed changes

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

adds the stub resolver abi pass #1036

adds the stub resolver abi pass #1036

gitoleg commented Jan 22, 2020 •

edited

Loading

ivg left a comment

ivg Jan 24, 2020

ivg commented Jan 24, 2020

ivg left a comment

ivg left a comment

ivg Apr 13, 2020

ivg Apr 13, 2020

ivg Apr 13, 2020

ivg Apr 14, 2020

ivg commented Apr 14, 2020 •

edited

Loading

ivg Apr 16, 2020

ivg Apr 16, 2020

ivg Apr 16, 2020

ivg Apr 16, 2020

ivg Apr 16, 2020

ivg commented Apr 17, 2020

ivg Jun 10, 2020


		(** [with_dst jmp d] updates jump's intra-procedural destination *)
		val with_dst : t -> dst option -> t

		@@ -1 +1,3 @@
		int __libc_start_main(int (main) (int, char , char ), int, char , void auxv);

		void __stack_chk_fail(void) __attribute__((noreturn));

adds the stub resolver abi pass #1036

adds the stub resolver abi pass #1036

Conversation

gitoleg commented Jan 22, 2020 • edited Loading

ivg left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ivg commented Jan 24, 2020

ivg left a comment

Choose a reason for hiding this comment

ivg left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ivg commented Apr 14, 2020 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ivg commented Apr 17, 2020

Choose a reason for hiding this comment

gitoleg commented Jan 22, 2020 •

edited

Loading

ivg commented Apr 14, 2020 •

edited

Loading