Trace alignment: thousands of sections, stack-management warnings

[MCher]

I collect passing/failing traces for a process. The failing case
causes an Application Verifier stop, whereupon Windbg kicks in. I note
the thread ID then look at the procmon trace: the faulting thread's
procmon trace has very specific characteristics, different from those
of all other threads. So I find the equivalent thread in the passing
process's procmon trace without any ambiguity. I then extract the two
per-thread tracecap traces and align them. The result has 3800 aligned/
disaligned sections and lots of warnings like "At final instruction
NNNNNNNN before divergence, nothing was pushed onto stack!". Many of
the aligned/disaligned sections consist of very few instructions. Two
experiments on two different inputs lead to the same result, so no
fluke. I run with trace_only_after_first_taint and use faint_file. The
whole-process traces are 4 and 16GB, respectively.

It certainly seems from procmon traces that thread roles in the app
are fixed, so I expected a much more compact alignment (and no
warnings!). Any comments on the sanify of x_y.aligned.txt? If
alignment has failed, any remedies? Regards,
--Mike

[Noah]

In general, a large number of aligned/disaligned regions is not
uncommon, especially for complex programs (our traces for Adobe Reader
had as many as ~1000 disaligned regions, and they were much smaller
than your 4GB traces). In such cases, additional techniques are needed
to identify the regions that are of interest for your particular
analysis.

Why are there so many? In addition to the execution differences caused
by the input differences (which is what I presume you are most
interested in), there are other factors increase the number of aligned/
disaligned regions: non-determinism, scheduling differences/
interactions from the other threads, etc. The exact effect of these
factors will vary for each program; to get an idea for how many of the
3800 regions can be accounted to these in your particular case, try
collecting two different traces using identical inputs and align them.
How many disaligned regions are there?

The warning about nothing being pushed onto the stack indicates the
presence of certain types of unstructured control flow, for example
due to interrupt instructions, setjmp/longjmp calls, rep instructions,
etc. These cases are handled by the tracealign tool so it is probably
not affecting the correctness of the results, but you can look into
each case (the warning message prints the instruction in question) if
you have concerns.

-Noah