App-side shadow memory.

[Lawliar]

• MCU Embedded App side shadow

• In the MCU's side, we use 1 bit of shadow memory to memorize the symbolic state of 1 byte of RAM. This has a 1/8 RAM overhead.

• However, inspired by ASAN, a 8-Byte RAM only has 9 different symbolic states. So, essentially, we only need 4 bit (i.e., 16 different states) instead of 8 bit (i.e., 255 different states) for the symbolic state of 8 Bytes. Besides, we do not need the extra 255 - 9 different states to store other metadata.

• Workstation App side shadow

• Workstation, compared to firmware, has a nearly endless RAM. Although there are certain benefits for allocating a huge chunk of shadow when the app launches (i.e., like what ASAN does), such as, faster look-up time. I overall do not see much benefits to do that for apps on workstation. We already have a huge shadow at the backend already.

• To align with SymCC's shadow, I found dynamically allocating app-side shadow more suitable. Like what SymCC does for its symbolic expressions.

• Although C++'s STL map aligns pretty well with this dynamic map, however, it introduces c++ code into the existing runtime in C. There is no issue with mixing C and C++ for application code, as long as it runs; for library code which applications links against, the symbol table is preferable to be as clean as possible. So, we can have a hashmap in C instead.

• In terms of granularity, I would opt for this 8:1 for simplicity first, and will try 16:1 (i.e., 8 bytes vs 4 bits) if it yeilds promising results.