k4st

The Pizlo special approach sounds a bit like converting out of SSA form via compensating `alloca`s in LLVM. E.g. one `alloca` per SSA variable, with a `store` into the `alloca` in the source block, and the `phi` replaced by a `load`.

If this is the case, this is an approach I've taken in the past to unify how LLVM-based taint tracking instrumentation of "normal" `alloca`s and phi nodes works, e.g.: https://github.com/lifting-bits/vmill/blob/master/tools/Tain...

What was his solution?

I created a monster, then a primordial explosion, then a nested simulation within the mind of the monster, and asked it to describe the physics of this nested simulation. Very engrossing.

Cool! You might even be able to run Rellic [1,2] on the LLVM IR produced by Clang when compiling Objective-C code. If it works, this will spit out goto-free C code, not C++.

[1] https://github.com/lifting-bits/rellic

[2] https://blog.trailofbits.com/2022/05/17/interactive-decompil...

It would certainly not hurt performance to emit a compiler warning about deleting the if statement testing for signed overflow, or about optimizing away the possible null pointer dereference in Do().

I think that the nature of Clang and LLVM makes this kind of reporting non-trivial / non-obvious. Deletions of this form may manifest as a result of multiple independent optimizations being brought to bear, culminating in noticing a trivially always-taken, or never-taken branch. Thus, deletion is the just the last step of a process, and at that step, the original intent of the code (e.g. an overflow check) has been lost to time.

Attempts to recover that original intent are likely to fail. LLVM instructions may have source location information, but these are just file:line:column triples, not pointers to AST nodes, and so they lack actionability: you can't reliably go from a source location to an AST node. In general though, LLVM's modular architecture means that you can't assume the presence of an AST in the first place, as the optimization may be executed independent of Clang, e.g. via the `opt` command-line tool. This further implies that the pass may operate on a separate machine than the original LLVM IR was produced, meaning you can't trust that a referenced source file even exists. There's also the DWARF metadata, but that's just another minefield.

Perhaps there's a middle ground with `switch`, `select`, or `br` instructions in LLVM operating on `undef` values, though.

At Trail of Bits, we've been working on this type of IR for C and C++ code [1]. We operate as a kind of Clang middle end, taking in a Clang AST, and spitting LLVM IR that is Clang-compatible out the other end. In this middle area, we progressively lower from a high-level MLIR dialect down to LLVM.

[1] https://github.com/trailofbits/vast

I created a datalog engine a few years back called Dr. Lojekyll: https://www.petergoodman.me/docs/dr-lojekyll.pdf

It was pretty cool; you could stream in new facts to it over time and it would incrementally and differentially update itself. The key idea was that I wanted the introduction of ground facts to be messages that the database reads (e.g. off of a message bus), and I wanted the database to be able to publish its conclusions onto the same or other message buses. I also wanted to be able to delete ground facts, which meant it could publish withdrawals of the prior-published conclusions. A lot of it was inspired by Frank McSherry's work, although I didn't use timely or differential dataflow. In retrospect I probably should have!

This particular system isn't used anymore because we made a classic monotonicity mistake by making it the brain of a distributed system, and then having it publish and receive messages with a bunch of microservices. The internal consistency model of the datalog engine didn't extend out to the microservices, and the possibility of feedback loops in the system meant that the whole thing could lie to itself and diverge uncontrollably! Despite this particular application of the engine being a failure, the engine itself worked quite well and I hope to one day return to datalog.

I think what a lot of people miss with datalog, and what becomes apparent as you use it more, is just how unpredictable many engines can be with the execution behavior of rules. This is the same problem that you have with a database, where the query planner makes a bad choice or where you lack an index, and so performance is bad. But with datalog, the composition of rules that comes so naturally also tends to compound this issue, resulting in time spent trying to chase down weird performance things and doing spooky re-ordering of your clause bodies to try to appease whatever choices the engine makes.

Typo fixed! Thanks :-)

I think the next big problems for MLIR to address are things like: metadata/location maintenance when integrating with third-party dialects and transformations. With LLVM optimizations, getting the optimization right has always seemed like the top priority, and then maybe getting metadata propagation working came a distant second.

I think the opportunity with MLIR is that metadata/location info can be the old nodes or other dialects. In our work, we want a tower/progression of IRs, and we want them simultaneously in memory, all living together. You could think of the debug metadata for a lower level dialect being the higher level dialect. This is why I sometimes think about LLVM IR as really being two IRs: LLVM "code" and metadata nodes. Metadata nodes in LLVM IR can represent arbitrary structures, but lack concrete checks/balances. MLIR fixes this by unifying the representations, bringing in structure while retaining flexibility.

At Trail of Bits, we are creating a new compiler front/middle end for Clang called VAST [1]. It consumes Clang ASTs and creates a high-level, information-rich MLIR dialect. Then, we progressively lower it through various other dialects, eventually down to the LLVM dialect in MLIR, which can be translated directly to LLVM IR.

Our goals with this pipeline are to enable static analyses that can choose the right abstraction level(s) for their goals, and using provenance, cross abstraction levels to relate results back to source code.

Neither Clang ASTs nor LLVM IR alone meet our needs for static analysis. Clang ASTs are too verbose and lack explicit representations for implicit behaviours in C++. LLVM IR isn't really "one IR," it's a two IRs (LLVM proper, and metadata), where LLVM proper is an unspecified family of dialects (-O0, -O1, -O2, -O3, then all the arch-specific stuff). LLVM IR also isn't easy to relate to source, even in the presence of maximal debug information. The Clang codegen process does ABI-specific lowering takes high-level types/values and transforms them to be more amenable to storing in target-cpu locations (e.g. registers). This actively works against relating information across levels; something that we want to solve with intermediate MLIR dialects.

Beyond our static analysis goals, I think an MLIR-based setup will be a key enabler of library-aware compiler optimizations. Right now, library-aware optimizations are challenging because Clang ASTs are hard to mutate, and by the time things are in LLVM IR, the abstraction boundaries provided by libraries are broken down by optimizations (e.g. inlining, specialization, folding), forcing optimization passes to reckon with the mechanics of how libraries are implemented.

We're very excited about MLIR, and we're pushing full steam ahead with VAST. MLIR is a technology that we can use to fix a lot of issues in Clang/LLVM that hinder really good static analysis.

[1] https://github.com/trailofbits/vast

I've always assumed that the `0x` prefix is to make copy & paste easier, i.e. so that you can copy the number, then immediate use it in a a C- or C++-like expression.

I work on a Google Test-like unit testing framework called DeepState [1] that gives you access to fuzzing and symbolic execution from your C or C++ unit tests. We have a tutorial [2] describing how to use it. It's new and still under development, but shows massive potential, and really brings these software security tools into a more developer-centric workflow.

[1] https://github.com/trailofbits/deepstate [2] http://www.petergoodman.me/docs/secdev-2018-slides.pdf

The [follow up](http://lists.llvm.org/pipermail/cfe-dev/2018-April/057672.ht...) message suggests that Google already internally using a non-JSPN-RPC transport layer.

You can also run KLEE on x86(-64) or AArch64 binaries using McSema to lift the binary to LLVM bitcode. An example is here: https://github.com/trailofbits/mcsema/tree/master/examples/M...

No, it's closer to [m]achine [c]ode [sema]ntics.

Indeed! I think I missed that in the original algorithm it doesn't wait for all slots to be zero, just that each slot go to zero. In that way it is just like waiting for each reader to go through a period of quiescence. This is a lot like the the version of rcu where the writer shuttles itself across cpus to use syscalls returns as a proxy for knowing that a particular cpu is not in any read side critical sections.

If there were a nice way to swap out the counters then summing would work, unfortunately that introduces an even bigger race :-(

Thanks for the correction!

That is fine ;-) Sum up the counters.

A nice simplification of would be to use the current CPU number as your ID. That eliminates the dependence on thread-local storage, and with high probability avoids issues where there are collisions between threads whose IDs modulo N are equivalent.

You could use an instruction like `RDTSC` to extract the CPU number. There might also be ways of getting at it efficiently with glibc/pthreads.

I have used TDOP and made variations of it before (e.g. combining TDOP and PEG, as well as introducing a form sub-grammars, like what you get with CFGs). I could also see the similarity between TDOP and left corner parsing, which gave me a better grounding on it.

Still never really felt like I deeply understood it. I think there was some intuitive leap I just wasn't making. A lot of it had to do with the choice of left/right binding powers, and loop that does the comparison and chooses whether to keep extending or to "dive down" into a new sub-tree.

Perhaps if there was a slightly different formulation, or something that was just a plain obvious description or methodology for getting the numbers right I would finally get it.

I use this frequently and it's pretty awesome. The killer combination for me is usually to set a hardware watchpoint, then reverse-continue. This is super useful when you've got a bit of memory corruption (e.g. buffer overflow) but don't know what's causing it.

Sounds like you want the BlackBerry hub :-P It's got both forms of views ;-)

Seems to be a dynamic binary translator. If you like these types of things, then check out Valgrind, Intel PIN, DynamoRIO, or QEMU.

I semi-recently implemented a malloc tester (am TAing an OS course). Students write their own implementation of malloc and free, and then I "intercept" their calls to brk and sbrk by using macros to re-define those symbols as my own versions of those functions.

It is quite nice: I have knobs to "fuzz" the alignment of returned addresses from sbrk, as well as to inject arbitrary EAGAINs, to see if they're following the man pages. Another thing that I looked for was re-entrancy. This was a bit hand-wavy, but ultimately took the form of a try-lock in my sbrk implementation, where if the try-lock fails, their invocations of sbrk are not being synchronized.

Another thing I did to evaluate their implementations was to poison the entire unallocated and allocated sbrk space, poison all allocated memory blocks that my test runner allocates, and poison all freed memory blocks before my test runner frees memory. This all enabled me to estimate the meta-data overhead of their malloc implementation at a byte-granularity. That is, I can search the sbrk space for the various poisons, and then report on their relative frequency. If the sum of the frequencies is under 100%, then I claim the remaining percent as meta-data overhead.

The poisoning also also allowed me to detect simple bugs: if they write beyond the returned sbrk pointer, then I can potentially catch that because the values in memory don't match the expected poison.

Overall, it was fun to do and I could present some nice stats. For example, I produced a histogram of malloc call sizes and sbrk call sizes. This allowed one to quickly see if they're invoking sbrk unnecessarily often.

This program appears to use heap allocation, at least indirectly through its use of std::string.

On a more general note, libraries that perform zero dynamic allocation (and instead require the library user to pass in memory) can be very convenient for systems programming where portability is a concern. For example, I use Intel XED instruction encoder/decoder, which is a library that performs no dynamic memory allocation. This allows me to use it in user space and kernel space without hijacking the malloc symbol.

I'm trying to solve a few related high-level problems. One, is that I want Valgrind-like debugging for the kernel. In my last kernel DBT system, I was able to do some pretty neat things, but actually using the DBT system was hell. A lot of this had to do with some of my poor design decisions (e.g. quick hacks that revealed interesting research areas, but were never refactored into good code).

Another problem that I want to solve is turn on/off pervasive profiling. This will sound similar to kprobes / systemtap / dtrace / etc, but what I want you to think about is something like "tainting" some objects (like injecting radioactive die) and then being able to observe their entire lifetime. I want to make it easy for someone without 1) domain specific knowledge of parts of the kernel, and 2) the ability to change the kernel source code to be able to answer the following types of questions: "if I write some data to a socket, how long does it take that data to go out over the wire, where are hold ups, etc."

Specifically for DBT, you hit the nail on the head: I am patching jumps in the code cache to point to other blocks in the code cache. Your suggestion is analogous to a copy-on-write tree/graph. I will have to think more on it, as it is interesting.

If you're curious about my project, then feel free to reach out to me :-) My email is on my HN profile.

Good to know! I'm in a funny place in my research project where I recently found out about the limitations of cross-modifying code. I had previously assumed that everything would work out for the best (doing hot-code patching in a DBT system that runs in kernel space), and didn't (appear to) face issues on the last version of my DBT system. For the next version, I'd like to play things safer. However, I suppose I could transparently recover from GP faults, as this is something I already do for other scenarios.

Do you have any suggestions (besides stop_machine-like IPIs for synchronizing all CPUs) on how to go about dynamic code patching in a JIT-based DBT-system? In my case, it's a priori unclear on whether or not the instruction being patched has been prefetched by another core.

My understanding is that the semantics are not as strong as they appear, although I have no experience with other architectures, so what is said to be the case and what is the case might still be relatively easier to use than other ISAs.

The optimization and software developer manuals suggest that self- and cross-modifying code must always be used with a synchronizing instruction (e.g. CPUID).

Also, this LKML discussion (https://lkml.org/lkml/2009/3/2/194) suggests that only modifying the first byte of an instruction with an int3 is safe, whereas modifying the other parts of an instruction can result in spurious faults when that instruction is next executed, unless the correct algorithm is followed.

And that's what emulation and binary translation are for! :-P

Would be really cool if this gave more explanation for the encodings. For example, showing the opcode, mod/reg/rm, and displacement components is really cool. What would be even cooler is to say why some bit or combination of bits makes this opcode use, for example, the rax register. This would be more an effort of exposing some tables, referencing manuals, etc. but I think it would give people more of an intuition for the encoding. Another thing to consider would be breaking the encoding down into octal digits instead of hex or binary (or maybe mix when appropriate) to give the most clear presentation of the encoding format. I could see this as a great way to lazily learn.

As someone who was 'pwned' by the Adobe leak, I have no idea how bad the pwnage was. That is, I don't recall what my Adobe password was, and so I have no idea which of my many passwords was compromised.

Also, I partially went through the Adobe password reset procedure two or three times--each time guessing at what my original password was. Unfortunately, they accepted all of my guesses, so I was still none the wiser about which password was compromised.

To top the entire ordeal off, Adobe was not the one to tell me that my password was compromised. Instead, my hosting provider and some other services notified me.

Dynamic binary translation can sometimes get performance improvements. This is because you would still statically compile your program, and then at runtime, the DBT system dynamically decodes and re-encodes the binary instructions. With a DBT system, you can do tracing, by identifying hot paths and such and lining those basic blocks up in your code cache.