DSA overlapping accesses

[sadrabt]

DSA should be able to recognize and overlapping access. (ie if two addresses are read into 128 bit register, stored in memory and then accessed separately). https://github.com/UQ-PAC/BASIL/pull/222#issuecomment-2337117908

R31 + 0x10 refers to a stack element node with two cells. One at offset 0 (R31 + 0x10) and one at offset 8(R31 + 0x18). The issue here is that the analysis doesn't merge the cell for add_six with the second cell in of R31 + 0x10 node since it can't yet tell the 128 bit reads add_six as well as add_two.

Each global is represented using separate node. the analysis currently merges add_two's node with the node of the stack position.

On possibility would be to represent globals that have overlapping accesses as one node. similar to the stack. ( i think this is only safe if we we can find all the accesses to the globals to soundly do this) however unlike the stack we can't find all accesses locally (even indirect stack references can't be found without a pointer analysis). Alternatively we can group consecutive globals into one node.

// 0x10DC0 contains a pointer to the procedure add_two
// 0x10DC8 contains a pointer to the procedure add_six
00000404: R8 := R8 + 0xDC0
// loading 128 bits from 0x10DC0 loads both the 64-bit pointer at address 0x10DC0
// and the 64-bit pointer at address 0x10DC8 to V0, concatenated together
0000040b: V0 := mem[R8, el]:u128
// storing V0 to the stack stores the pointer to add_two at R31 + 0x10 and the pointer to add_six at R31 + 0x18
00000413: mem := mem with [R31 + 0x10, el]:u128 <- V0
0000041a: R8 := mem[R8 + 0x10, el]:u64
00000422: mem := mem with [R31 + 0x20, el]:u64 <- R8
00000429: R8 := mem[R31 + 0x10, el]:u64
0000042e: R30 := 0x7D0
00000431: call R8 with return %00000433

00000433:
// the DSA says that R8 at this assignment points to node 434 which is empty, but it should point to add_six
// or alternatively some node that represents that the pointers to add_two and add_six were loaded together and stored on the stack together
00000438: R8 := mem[R31 + 0x18, el]:u64
0000043d: R30 := 0x7D8
00000440: call R8 with return %00000442

[sadrabt]

indirect overlapping accesses are also an issue:

R0 = G + 8  // where G is base address for the heap
R1 = G + 12 // two consecutive globals
R2 = Malloc()
*R2 = R0 // 64 bit write
R3 = *R2  // 64 bit read
R4 = *R3 // 128 bit read