Counterfactual Debugging: Dereference Fixpoints
Imagine we have the following arrangements in memory:
address: value
where value == address, so we have effectively:
address: address
So when we dereference the address we get the address value. If we name the dereference function as p(address) we get
p(address) = address
That gave me an idea to name after the mathematical notion of a function fixpoint (fixed point).
In C++ we can write the following code to initialize a fixpoint:
void *pc = &pc;
in assembly language:
lea eax, [pc]
mov dword ptr [pc], eax
or using local variables:
lea eax, [ebp-4]
mov dword ptr [ebp-4], eax
Dereference of a fixpoint pointer gives us the same value as its address, for example, using old style conversion:
int *pc = (int *)&pc;
if (pc == (int *)*pc) {
// TRUE
or for C++ purists:
int *pc = reinterpret_cast<int *>(&pc);
if (pc == reinterpret_cast<int *>(*pc)) {
// TRUE
In x86 assembly language we have this comparison:
mov eax,dword ptr [pc]
mov ecx,dword ptr [pc]
cmp ecx,dword ptr [eax]
or using local variables:
mov eax,dword ptr [ebp-4]
mov ecx,dword ptr [ebp-4]
cmp ecx,dword ptr [eax]
Now, having discussed fixpoints, let me ask the question to ponder over this weekend. What would this code do?
int _tmain(int argc, _TCHAR* argv[])
{
char c;
char* pc = &c;
while(1)
{
*pc = 0;
pc++;
}
return 0;
}
Would it produce stack overflow with an exception, or stack underflow with an exception or loop indefinitely? The C++ Standard answer of compiler and platform dependence is not acceptable. I plan to elaborate on this topic on Monday.
The notion of counterfactual debugging (”what if” debugging) was inspired by the so called counterfactual history.
- Dmitry Vostokov @ DumpAnalysis.org -
September 11th, 2009 at 5:35 pm
It will overwrite the thread stack with zeros and it will crash with access violation when reaching StackBase.
September 12th, 2009 at 12:59 am
>if (pc == (int *)*pc) {…}
Shouldn’t that be “if (&pc == (int**)pc) {…}”?
Otherwise, this comparison can _reliable_ tell what ‘pc’ is a pointer to the fixpoint, not a fixpoint itself, right?
>overflow with an exception, or stack underflow with an exception or loop indefinitely?
Our guess is what if this code will be optimized, it will almost certainly lead to underflow in all situations. But for usual non-optimized “all vars are volatile vars” fetches – this single loop definitely produces lot’s of possibilities
September 14th, 2009 at 10:54 am
Both comparisons do the same thing in the case of a fixpoint and any multiple dereferencing by definition of a fixpont:
if (&pc == (int **)*(int *)*pc)
mov eax,dword ptr [pc]mov ecx,dword ptr [eax]
lea edx,[pc]
cmp edx,dword ptr [ecx]
Originally I myself believed in underflow in all situations until I suddenly got an infinite loop. I couldn’t believe my eyes and after the investigation as a byproduct I came to the definition of a fixpoint. I plan to write more about this later today.
September 15th, 2009 at 9:19 pm
[…] discussed dereference fixpoints we come back to the quiz code and see what happens when we execute it after compilation as default […]
September 19th, 2009 at 11:28 pm
Yeah, in case of fixpoint both comparisons indeed are the same. We tried to say what extra-indirection-level comparison will return true even if ‘pc’ is not a fixpoint itself – but rather a pointer to the fixpoint.
Example:
init:
lea eax, [pcx]
mov [eax], eax ; pcx is a fixpoint now
mov [pc], eax ; ‘pc’ and ‘pcx’ have different addresses
check0:
lea eax, [pc]
mov ecx, [eax]
cmp eax, ecx
je PcIsFixpoint ; check will fail
check1:
mov eax, [pc]
mov ecx, [eax]
cmp eax, ecx
je PcIsFixpointOrPointerToFixpoint ; check will succeed
Btw,.. This blog is awesome
September 22nd, 2009 at 4:26 pm
Thanks! Dmitry
January 8th, 2010 at 9:36 am
[…] Pointers and their links are also objects and arrows to form a category, called MemP(tr). The following picture illustrates it with the last pointer shown as a dereference fixpoint: […]
August 18th, 2010 at 3:45 pm
[…] class memory layout I made sure that it points to the same heap address by making vtable pointer a dereference fixpoint. Here is a source code based on how Visual C++ compiler implements objects in […]