Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #31239 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-04-17 09:17 -0500 |
| Last post | 2021-04-19 13:47 -0400 |
| Articles | 17 on this page of 37 — 6 participants |
Back to article view | Back to comp.theory
Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 09:17 -0500
Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 19:18 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-18 02:02 +0000
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 21:04 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-18 02:19 +0000
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 21:24 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-17 19:05 -0700
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 21:12 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-17 19:18 -0700
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 03:08 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 21:16 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 21:56 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-18 16:08 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-18 14:21 -0700
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-18 14:22 -0700
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-19 01:11 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-18 19:32 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-19 01:38 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-18 19:52 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-19 02:10 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-18 19:57 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-18 20:47 -0700
Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 01:34 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 19:37 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 02:13 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 20:28 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 02:49 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 21:01 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 19:49 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 02:36 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 20:43 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 13:21 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 23:30 +0100
Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 13:24 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong) Mikko <mikko.levanto@outlook.com> - 2021-04-19 19:43 +0300
Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-19 11:53 -0500
Re: Infinite recursion detection criteria (Please correct me if I am wrong) Richard Damon <Richard@Damon-Family.org> - 2021-04-19 13:47 -0400
Page 2 of 2 — ← Prev page 1 [2]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-18 19:57 -0500 |
| Subject | Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) |
| Message-ID | <nsOdnaUqY4vuSOH9nZ2dnUU7-K-dnZ2d@giganews.com> |
| In reply to | #31409 |
On 4/18/2021 7:38 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 4/18/2021 7:11 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> It took me more that a few minutes to understand that the AT&T operand >>>> order is reversed. Then I discovered that the RIP relative addressing >>>> was used like a jump table when a value was assigned to the RIP >>>> register. >>> >>> RIP is a red-herring. The code is compiled from standard C. If I >>> compile it for the 32-bit architecture, no IP relative addressing is >>> used, but the pattern of calls remains the same. >> >> 0x000055555555517d <main+0>: endbr64 >> 0x0000555555555181 <main+4>: push %rbp >> 0x0000555555555182 <main+5>: mov %rsp,%rbp >> 0x0000555555555185 <main+8>: callq 0x555555555129 <Y> >> 0x0000555555555129 <Y+0>: endbr64 >> 0x000055555555512d <Y+4>: push %rbp >> 0x000055555555512e <Y+5>: mov %rsp,%rbp >> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >> >> The above instruction moves the contents of the edx register into an >> offset relative to the rip (instruction pointer register). This could >> easily make self-modifying code. > > However it does not. RIP is a red-herring. The code is compiled from > standard C. If I compile it for the 32-bit architecture, no IP relative > addressing is used, but the pattern of calls remains the same. > Simply post the C source. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2021-04-18 20:47 -0700 |
| Subject | Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) |
| Message-ID | <s5iug5$15af$1@gioia.aioe.org> |
| In reply to | #31413 |
On 4/18/2021 5:57 PM, olcott wrote: > On 4/18/2021 7:38 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 4/18/2021 7:11 PM, Ben Bacarisse wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> It took me more that a few minutes to understand that the AT&T operand >>>>> order is reversed. Then I discovered that the RIP relative addressing >>>>> was used like a jump table when a value was assigned to the RIP >>>>> register. >>>> >>>> RIP is a red-herring. The code is compiled from standard C. If I >>>> compile it for the 32-bit architecture, no IP relative addressing is >>>> used, but the pattern of calls remains the same. >>> >>> 0x000055555555517d <main+0>: endbr64 >>> 0x0000555555555181 <main+4>: push %rbp >>> 0x0000555555555182 <main+5>: mov %rsp,%rbp >>> 0x0000555555555185 <main+8>: callq 0x555555555129 <Y> >>> 0x0000555555555129 <Y+0>: endbr64 >>> 0x000055555555512d <Y+4>: push %rbp >>> 0x000055555555512e <Y+5>: mov %rsp,%rbp >>> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >>> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >>> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >>> >>> The above instruction moves the contents of the edx register into an >>> offset relative to the rip (instruction pointer register). This could >>> easily make self-modifying code. >> >> However it does not. RIP is a red-herring. The code is compiled from >> standard C. If I compile it for the 32-bit architecture, no IP relative >> addressing is used, but the pattern of calls remains the same. >> > > Simply post the C source. > Iirc, Kaz has already implemented some of your stuff in C. Btw, have you ever heard of a site called GodBolt? https://godbolt.org Its really nice.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-04-18 01:34 +0100 |
| Message-ID | <87y2dg8m7i.fsf@bsb.me.uk> |
| In reply to | #31239 |
olcott <NoOne@NoWhere.com> writes: > If a function X() is called by function Y() twice in sequence from the > same machine address of Y() with the same parameters to X() and the > execution trace shows no conditional branch instructions in Y() or > function call returns in X() then the function call from Y() to X() is > infinitely recursive unless X() stops it. You mean like this: 0x000055555555517d <main+0>: endbr64 0x0000555555555181 <main+4>: push %rbp 0x0000555555555182 <main+5>: mov %rsp,%rbp 0x0000555555555185 <main+8>: callq 0x555555555129 <Y> 0x0000555555555129 <Y+0>: endbr64 0x000055555555512d <Y+4>: push %rbp 0x000055555555512e <Y+5>: mov %rsp,%rbp 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Y+23>: cltq 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Y+44>: callq *%rax 0x000055555555515c <X+0>: endbr64 0x0000555555555160 <X+4>: push %rbp 0x0000555555555161 <X+5>: mov %rsp,%rbp 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> 0x0000555555555129 <Y+0>: endbr64 0x000055555555512d <Y+4>: push %rbp 0x000055555555512e <Y+5>: mov %rsp,%rbp 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Y+23>: cltq 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Y+44>: callq *%rax 0x000055555555515c <X+0>: endbr64 0x0000555555555160 <X+4>: push %rbp 0x0000555555555161 <X+5>: mov %rsp,%rbp 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> 0x0000555555555129 <Y+0>: endbr64 0x000055555555512d <Y+4>: push %rbp 0x000055555555512e <Y+5>: mov %rsp,%rbp 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Y+23>: cltq 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Y+44>: callq *%rax 0x000055555555515c <X+0>: endbr64 0x0000555555555160 <X+4>: push %rbp 0x0000555555555161 <X+5>: mov %rsp,%rbp 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> 0x0000555555555129 <Y+0>: endbr64 0x000055555555512d <Y+4>: push %rbp 0x000055555555512e <Y+5>: mov %rsp,%rbp 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Y+23>: cltq 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Y+44>: callq *%rax 0x000055555555515c <X+0>: endbr64 0x0000555555555160 <X+4>: push %rbp 0x0000555555555161 <X+5>: mov %rsp,%rbp 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> 0x0000555555555129 <Y+0>: endbr64 0x000055555555512d <Y+4>: push %rbp 0x000055555555512e <Y+5>: mov %rsp,%rbp 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Y+23>: cltq 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Y+44>: callq *%rax 0x000055555555516e <Z+0>: endbr64 0x0000555555555172 <Z+4>: push %rbp 0x0000555555555173 <Z+5>: mov %rsp,%rbp 0x0000555555555176 <Z+8>: mov $0x1,%eax ... Note how X is called from Y+44 more than once with no branching or returns. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-17 19:37 -0500 |
| Message-ID | <tLKdnTL0L96r4ub9nZ2dnUU7-d-dnZ2d@giganews.com> |
| In reply to | #31281 |
On 4/17/2021 7:34 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> If a function X() is called by function Y() twice in sequence from the >> same machine address of Y() with the same parameters to X() and the >> execution trace shows no conditional branch instructions in Y() or >> function call returns in X() then the function call from Y() to X() is >> infinitely recursive unless X() stops it. > > You mean like this: > I couldn't make that out it is not the syntax that I am familiar with does it get past this newly updated criteria? If the execution trace of function X() called by function Y() shows: (1) Function X() is called twice in sequence from the same machine address of Y(). (2) With the same parameters to X(). (3) With no conditional branch or indexed jump instructions in Y(). (4) With no function call returns from X(). then the function call from Y() to X() is infinitely recursive unless X() stops it. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-04-18 02:13 +0100 |
| Message-ID | <87czus8kdr.fsf@bsb.me.uk> |
| In reply to | #31283 |
olcott <NoOne@NoWhere.com> writes: > On 4/17/2021 7:34 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> If a function X() is called by function Y() twice in sequence from the >>> same machine address of Y() with the same parameters to X() and the >>> execution trace shows no conditional branch instructions in Y() or >>> function call returns in X() then the function call from Y() to X() is >>> infinitely recursive unless X() stops it. >> >> You mean like this: (I'll post a slight variation in case that clearer) > I couldn't make that out it is not the syntax that I am familiar with > does it get past this newly updated criteria? I was asking you because I don't follow your criteria. If neither Y not X return, of course there is infinite recursion. I thought the criteria were there to detect if there was infinite recursion without just waiting to see if X or Y return (which they'd have to do multiple times). In other words, I thought you were looking for calls without an intervening return. > If the execution trace of function X() called by function Y() shows: > (1) Function X() is called twice in sequence from the same machine > address of Y(). The calls are obvious -- look for callq instructions. Those from Y to X are all at Y+8 (in the new trace below). > (2) With the same parameters to X(). No parameters are being passed to any of the functions. > (3) With no conditional branch or indexed jump instructions in Y(). The only instructions in Y are push, mov and callq. If X returns (i.e. the recursion is not infinite) then Y will do pop and retq. > (4) With no function call returns from X(). X calls Q which calls back to Y so X can be called again. But if the recursion is not infinite, X will return to Y. > then the function call from Y() to X() is infinitely recursive unless > X() stops it. I thought the plan was to detect "infinite recursion" from the call sequence. I.e. that you can detect it from something like this trace: 0x0000555555555189 <main+0>: endbr64 0x000055555555518d <main+4>: push %rbp 0x000055555555518e <main+5>: mov %rsp,%rbp 0x0000555555555191 <main+8>: callq 0x55555555516b <Y> 0x000055555555516b <Y+0>: endbr64 0x000055555555516f <Y+4>: push %rbp 0x0000555555555170 <Y+5>: mov %rsp,%rbp 0x0000555555555173 <Y+8>: callq 0x55555555515c <X> 0x000055555555515c <X+0>: endbr64 0x0000555555555160 <X+4>: push %rbp 0x0000555555555161 <X+5>: mov %rsp,%rbp 0x0000555555555164 <X+8>: callq 0x555555555129 <Q> 0x0000555555555129 <Q+0>: endbr64 0x000055555555512d <Q+4>: push %rbp 0x000055555555512e <Q+5>: mov %rsp,%rbp 0x0000555555555131 <Q+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Q+14>: lea 0x1(%rax),%edx 0x000055555555513a <Q+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Q+23>: cltq 0x0000555555555142 <Q+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Q+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Q+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Q+44>: callq *%rax 0x000055555555516b <Y+0>: endbr64 0x000055555555516f <Y+4>: push %rbp 0x0000555555555170 <Y+5>: mov %rsp,%rbp 0x0000555555555173 <Y+8>: callq 0x55555555515c <X> 0x000055555555515c <X+0>: endbr64 0x0000555555555160 <X+4>: push %rbp 0x0000555555555161 <X+5>: mov %rsp,%rbp 0x0000555555555164 <X+8>: callq 0x555555555129 <Q> 0x0000555555555129 <Q+0>: endbr64 0x000055555555512d <Q+4>: push %rbp 0x000055555555512e <Q+5>: mov %rsp,%rbp 0x0000555555555131 <Q+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Q+14>: lea 0x1(%rax),%edx 0x000055555555513a <Q+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Q+23>: cltq 0x0000555555555142 <Q+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Q+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Q+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Q+44>: callq *%rax 0x000055555555516b <Y+0>: endbr64 0x000055555555516f <Y+4>: push %rbp 0x0000555555555170 <Y+5>: mov %rsp,%rbp 0x0000555555555173 <Y+8>: callq 0x55555555515c <X> 0x000055555555515c <X+0>: endbr64 0x0000555555555160 <X+4>: push %rbp 0x0000555555555161 <X+5>: mov %rsp,%rbp 0x0000555555555164 <X+8>: callq 0x555555555129 <Q> 0x0000555555555129 <Q+0>: endbr64 0x000055555555512d <Q+4>: push %rbp 0x000055555555512e <Q+5>: mov %rsp,%rbp 0x0000555555555131 <Q+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Q+14>: lea 0x1(%rax),%edx 0x000055555555513a <Q+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Q+23>: cltq 0x0000555555555142 <Q+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Q+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Q+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Q+44>: callq *%rax 0x000055555555516b <Y+0>: endbr64 0x000055555555516f <Y+4>: push %rbp 0x0000555555555170 <Y+5>: mov %rsp,%rbp 0x0000555555555173 <Y+8>: callq 0x55555555515c <X> 0x000055555555515c <X+0>: endbr64 0x0000555555555160 <X+4>: push %rbp 0x0000555555555161 <X+5>: mov %rsp,%rbp 0x0000555555555164 <X+8>: callq 0x555555555129 <Q> 0x0000555555555129 <Q+0>: endbr64 0x000055555555512d <Q+4>: push %rbp 0x000055555555512e <Q+5>: mov %rsp,%rbp 0x0000555555555131 <Q+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Q+14>: lea 0x1(%rax),%edx 0x000055555555513a <Q+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Q+23>: cltq 0x0000555555555142 <Q+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Q+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Q+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Q+44>: callq *%rax 0x000055555555516b <Y+0>: endbr64 0x000055555555516f <Y+4>: push %rbp 0x0000555555555170 <Y+5>: mov %rsp,%rbp 0x0000555555555173 <Y+8>: callq 0x55555555515c <X> 0x000055555555515c <X+0>: endbr64 0x0000555555555160 <X+4>: push %rbp 0x0000555555555161 <X+5>: mov %rsp,%rbp 0x0000555555555164 <X+8>: callq 0x555555555129 <Q> 0x0000555555555129 <Q+0>: endbr64 0x000055555555512d <Q+4>: push %rbp 0x000055555555512e <Q+5>: mov %rsp,%rbp 0x0000555555555131 <Q+8>: mov 0x2f15(%rip),%eax 0x0000555555555137 <Q+14>: lea 0x1(%rax),%edx 0x000055555555513a <Q+17>: mov %edx,0x2f0c(%rip) 0x0000555555555140 <Q+23>: cltq 0x0000555555555142 <Q+25>: lea 0x0(,%rax,8),%rdx 0x000055555555514a <Q+33>: lea 0x2ecf(%rip),%rax 0x0000555555555151 <Q+40>: mov (%rdx,%rax,1),%rax 0x0000555555555155 <Q+44>: callq *%rax ... -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-17 20:28 -0500 |
| Message-ID | <kvqdnQAdt47ZFub9nZ2dnUU7-efNnZ2d@giganews.com> |
| In reply to | #31287 |
On 4/17/2021 8:13 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 4/17/2021 7:34 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> If a function X() is called by function Y() twice in sequence from the >>>> same machine address of Y() with the same parameters to X() and the >>>> execution trace shows no conditional branch instructions in Y() or >>>> function call returns in X() then the function call from Y() to X() is >>>> infinitely recursive unless X() stops it. >>> >>> You mean like this: > > (I'll post a slight variation in case that clearer) > >> I couldn't make that out it is not the syntax that I am familiar with >> does it get past this newly updated criteria? > > I was asking you because I don't follow your criteria. If neither Y not > X return, of course there is infinite recursion. I thought the criteria > were there to detect if there was infinite recursion without just > waiting to see if X or Y return (which they'd have to do multiple > times). In other words, I thought you were looking for calls without an > intervening return. There are no returns in the execution trace. >> If the execution trace of function X() called by function Y() shows: >> (1) Function X() is called twice in sequence from the same machine >> address of Y(). > > The calls are obvious -- look for callq instructions. Those from Y to X > are all at Y+8 (in the new trace below). If my system does not work on the x64 architecture than I simply assume that I am only using the x86 architecture. >> (2) With the same parameters to X(). > > No parameters are being passed to any of the functions. > I am modeling the case where parameters are passed, so if no parameters are passed this is no good. >> (3) With no conditional branch or indexed jump instructions in Y(). > > The only instructions in Y are push, mov and callq. If X returns > (i.e. the recursion is not infinite) then Y will do pop and retq. > >> (4) With no function call returns from X(). > > X calls Q which calls back to Y so X can be called again. But if the > recursion is not infinite, X will return to Y. > In your x64 example. Can you do the same thing in x86? >> then the function call from Y() to X() is infinitely recursive unless >> X() stops it. > > I thought the plan was to detect "infinite recursion" from the call > sequence. I.e. that you can detect it from something like this trace: I am only working in Intel x86. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-04-18 02:49 +0100 |
| Message-ID | <87k0p07467.fsf@bsb.me.uk> |
| In reply to | #31289 |
olcott <NoOne@NoWhere.com> writes: > On 4/17/2021 8:13 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 4/17/2021 7:34 PM, Ben Bacarisse wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> If a function X() is called by function Y() twice in sequence from the >>>>> same machine address of Y() with the same parameters to X() and the >>>>> execution trace shows no conditional branch instructions in Y() or >>>>> function call returns in X() then the function call from Y() to X() is >>>>> infinitely recursive unless X() stops it. >>>> >>>> You mean like this: >> >> (I'll post a slight variation in case that clearer) >> >>> I couldn't make that out it is not the syntax that I am familiar with >>> does it get past this newly updated criteria? >> >> I was asking you because I don't follow your criteria. If neither Y not >> X return, of course there is infinite recursion. I thought the criteria >> were there to detect if there was infinite recursion without just >> waiting to see if X or Y return (which they'd have to do multiple >> times). In other words, I thought you were looking for calls without an >> intervening return. > > There are no returns in the execution trace. Ah, then it's a silly set of criteria. You can't detect anything other than by executing indefinitely to see if there is, eventually a return. Surely the plan is to be able to detect infinite recursion when the duplicate call is made, based on the there being identical parameters and no conditional jumps (and maybe some more details as well). I thought you had this sorted out already. > >>> If the execution trace of function X() called by function Y() shows: >>> (1) Function X() is called twice in sequence from the same machine >>> address of Y(). >> >> The calls are obvious -- look for callq instructions. Those from Y to X >> are all at Y+8 (in the new trace below). > > If my system does not work on the x64 architecture than I simply > assume that I am only using the x86 architecture. > >>> (2) With the same parameters to X(). >> >> No parameters are being passed to any of the functions. >> > > I am modeling the case where parameters are passed, so if no > parameters are passed this is no good. I could pass a few and it would make no difference. How many would I need to pass for you to bother paying attention? >>> (3) With no conditional branch or indexed jump instructions in Y(). >> >> The only instructions in Y are push, mov and callq. If X returns >> (i.e. the recursion is not infinite) then Y will do pop and retq. >> >>> (4) With no function call returns from X(). >> >> X calls Q which calls back to Y so X can be called again. But if the >> recursion is not infinite, X will return to Y. > > In your x64 example. Can you do the same thing in x86? I am not going to put in more work when it makes no difference. Anyone who know the Intel architecture can see that there is nothing significant in the bit width here. >>> then the function call from Y() to X() is infinitely recursive unless >>> X() stops it. >> >> I thought the plan was to detect "infinite recursion" from the call >> sequence. I.e. that you can detect it from something like this >> trace: > I am only working in Intel x86. You think the code does something magic that won't be the same in 32 bits? Or are you just looking for a reason not to bother checking your criteria? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-17 21:01 -0500 |
| Message-ID | <QaSdnZSATouWDub9nZ2dnUU7-R2dnZ2d@giganews.com> |
| In reply to | #31295 |
On 4/17/2021 8:49 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 4/17/2021 8:13 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> On 4/17/2021 7:34 PM, Ben Bacarisse wrote: >>>>> olcott <NoOne@NoWhere.com> writes: >>>>> >>>>>> If a function X() is called by function Y() twice in sequence from the >>>>>> same machine address of Y() with the same parameters to X() and the >>>>>> execution trace shows no conditional branch instructions in Y() or >>>>>> function call returns in X() then the function call from Y() to X() is >>>>>> infinitely recursive unless X() stops it. >>>>> >>>>> You mean like this: >>> >>> (I'll post a slight variation in case that clearer) >>> >>>> I couldn't make that out it is not the syntax that I am familiar with >>>> does it get past this newly updated criteria? >>> >>> I was asking you because I don't follow your criteria. If neither Y not >>> X return, of course there is infinite recursion. I thought the criteria >>> were there to detect if there was infinite recursion without just >>> waiting to see if X or Y return (which they'd have to do multiple >>> times). In other words, I thought you were looking for calls without an >>> intervening return. >> >> There are no returns in the execution trace. > > Ah, then it's a silly set of criteria. You can't detect anything other > than by executing indefinitely to see if there is, eventually a return. > Surely the plan is to be able to detect infinite recursion when the > duplicate call is made, based on the there being identical parameters > and no conditional jumps (and maybe some more details as well). > > I thought you had this sorted out already. > >> >>>> If the execution trace of function X() called by function Y() shows: >>>> (1) Function X() is called twice in sequence from the same machine >>>> address of Y(). >>> >>> The calls are obvious -- look for callq instructions. Those from Y to X >>> are all at Y+8 (in the new trace below). >> >> If my system does not work on the x64 architecture than I simply >> assume that I am only using the x86 architecture. >> >>>> (2) With the same parameters to X(). >>> >>> No parameters are being passed to any of the functions. >>> >> >> I am modeling the case where parameters are passed, so if no >> parameters are passed this is no good. > > I could pass a few and it would make no difference. How many would I > need to pass for you to bother paying attention? > >>>> (3) With no conditional branch or indexed jump instructions in Y(). >>> >>> The only instructions in Y are push, mov and callq. If X returns >>> (i.e. the recursion is not infinite) then Y will do pop and retq. >>> >>>> (4) With no function call returns from X(). >>> >>> X calls Q which calls back to Y so X can be called again. But if the >>> recursion is not infinite, X will return to Y. >> >> In your x64 example. Can you do the same thing in x86? > > I am not going to put in more work when it makes no difference. Anyone > who know the Intel architecture can see that there is nothing > significant in the bit width here. > >>>> then the function call from Y() to X() is infinitely recursive unless >>>> X() stops it. >>> >>> I thought the plan was to detect "infinite recursion" from the call >>> sequence. I.e. that you can detect it from something like this >>> trace: > >> I am only working in Intel x86. > > You think the code does something magic that won't be the same in 32 > bits? Or are you just looking for a reason not to bother checking your > criteria? > I know that the x64 architecture has rip relative addressing and this changes key things completely. If you don't want to translate it to x86 I may look at it some time later. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-17 19:49 -0500 |
| Message-ID | <saCdnS6GYdexH-b9nZ2dnUU7-NnNnZ2d@giganews.com> |
| In reply to | #31281 |
On 4/17/2021 7:34 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> If a function X() is called by function Y() twice in sequence from the >> same machine address of Y() with the same parameters to X() and the >> execution trace shows no conditional branch instructions in Y() or >> function call returns in X() then the function call from Y() to X() is >> infinitely recursive unless X() stops it. > > You mean like this: > > 0x000055555555517d <main+0>: endbr64 > 0x0000555555555181 <main+4>: push %rbp > 0x0000555555555182 <main+5>: mov %rsp,%rbp > 0x0000555555555185 <main+8>: callq 0x555555555129 <Y> > 0x0000555555555129 <Y+0>: endbr64 > 0x000055555555512d <Y+4>: push %rbp > 0x000055555555512e <Y+5>: mov %rsp,%rbp > 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax > 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx > 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) > 0x0000555555555140 <Y+23>: cltq > 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx > 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax > 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax > 0x0000555555555155 <Y+44>: callq *%rax > 0x000055555555515c <X+0>: endbr64 > 0x0000555555555160 <X+4>: push %rbp > 0x0000555555555161 <X+5>: mov %rsp,%rbp > 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> > 0x0000555555555129 <Y+0>: endbr64 > 0x000055555555512d <Y+4>: push %rbp > 0x000055555555512e <Y+5>: mov %rsp,%rbp > 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax > 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx > 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) > 0x0000555555555140 <Y+23>: cltq > 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx > 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax > 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax > 0x0000555555555155 <Y+44>: callq *%rax > 0x000055555555515c <X+0>: endbr64 > 0x0000555555555160 <X+4>: push %rbp > 0x0000555555555161 <X+5>: mov %rsp,%rbp > 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> > 0x0000555555555129 <Y+0>: endbr64 > 0x000055555555512d <Y+4>: push %rbp > 0x000055555555512e <Y+5>: mov %rsp,%rbp > 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax > 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx > 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) > 0x0000555555555140 <Y+23>: cltq > 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx > 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax > 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax > 0x0000555555555155 <Y+44>: callq *%rax > 0x000055555555515c <X+0>: endbr64 > 0x0000555555555160 <X+4>: push %rbp > 0x0000555555555161 <X+5>: mov %rsp,%rbp > 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> > 0x0000555555555129 <Y+0>: endbr64 > 0x000055555555512d <Y+4>: push %rbp > 0x000055555555512e <Y+5>: mov %rsp,%rbp > 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax > 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx > 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) > 0x0000555555555140 <Y+23>: cltq > 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx > 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax > 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax > 0x0000555555555155 <Y+44>: callq *%rax > 0x000055555555515c <X+0>: endbr64 > 0x0000555555555160 <X+4>: push %rbp > 0x0000555555555161 <X+5>: mov %rsp,%rbp > 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> > 0x0000555555555129 <Y+0>: endbr64 > 0x000055555555512d <Y+4>: push %rbp > 0x000055555555512e <Y+5>: mov %rsp,%rbp > 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax > 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx > 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) > 0x0000555555555140 <Y+23>: cltq > 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx > 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax > 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax > 0x0000555555555155 <Y+44>: callq *%rax > 0x000055555555516e <Z+0>: endbr64 > 0x0000555555555172 <Z+4>: push %rbp > 0x0000555555555173 <Z+5>: mov %rsp,%rbp > 0x0000555555555176 <Z+8>: mov $0x1,%eax > ... > > Note how X is called from Y+44 more than once with no branching or > returns. > Lets simply assume x86 architecture and Intel syntax. This is my latest revised infinite recursion halt deciding criteria: If the execution trace of function X() called by function Y() shows: (1) Function X() is called twice in sequence from the same machine address of Y(). (2) With the same parameters to X(). (3) With no conditional branch or indexed jump instructions in Y(). (4) With no function call returns from X(). then the function call from Y() to X() is infinitely recursive unless X() stops it. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-04-18 02:36 +0100 |
| Message-ID | <87pmys74sc.fsf@bsb.me.uk> |
| In reply to | #31286 |
olcott <NoOne@NoWhere.com> writes: > On 4/17/2021 7:34 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> If a function X() is called by function Y() twice in sequence from the >>> same machine address of Y() with the same parameters to X() and the >>> execution trace shows no conditional branch instructions in Y() or >>> function call returns in X() then the function call from Y() to X() is >>> infinitely recursive unless X() stops it. >> >> You mean like this: >> >> 0x000055555555517d <main+0>: endbr64 >> 0x0000555555555181 <main+4>: push %rbp >> 0x0000555555555182 <main+5>: mov %rsp,%rbp >> 0x0000555555555185 <main+8>: callq 0x555555555129 <Y> >> 0x0000555555555129 <Y+0>: endbr64 >> 0x000055555555512d <Y+4>: push %rbp >> 0x000055555555512e <Y+5>: mov %rsp,%rbp >> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >> 0x0000555555555140 <Y+23>: cltq >> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >> 0x0000555555555155 <Y+44>: callq *%rax >> 0x000055555555515c <X+0>: endbr64 >> 0x0000555555555160 <X+4>: push %rbp >> 0x0000555555555161 <X+5>: mov %rsp,%rbp >> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> >> 0x0000555555555129 <Y+0>: endbr64 >> 0x000055555555512d <Y+4>: push %rbp >> 0x000055555555512e <Y+5>: mov %rsp,%rbp >> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >> 0x0000555555555140 <Y+23>: cltq >> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >> 0x0000555555555155 <Y+44>: callq *%rax >> 0x000055555555515c <X+0>: endbr64 >> 0x0000555555555160 <X+4>: push %rbp >> 0x0000555555555161 <X+5>: mov %rsp,%rbp >> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> >> 0x0000555555555129 <Y+0>: endbr64 >> 0x000055555555512d <Y+4>: push %rbp >> 0x000055555555512e <Y+5>: mov %rsp,%rbp >> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >> 0x0000555555555140 <Y+23>: cltq >> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >> 0x0000555555555155 <Y+44>: callq *%rax >> 0x000055555555515c <X+0>: endbr64 >> 0x0000555555555160 <X+4>: push %rbp >> 0x0000555555555161 <X+5>: mov %rsp,%rbp >> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> >> 0x0000555555555129 <Y+0>: endbr64 >> 0x000055555555512d <Y+4>: push %rbp >> 0x000055555555512e <Y+5>: mov %rsp,%rbp >> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >> 0x0000555555555140 <Y+23>: cltq >> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >> 0x0000555555555155 <Y+44>: callq *%rax >> 0x000055555555515c <X+0>: endbr64 >> 0x0000555555555160 <X+4>: push %rbp >> 0x0000555555555161 <X+5>: mov %rsp,%rbp >> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> >> 0x0000555555555129 <Y+0>: endbr64 >> 0x000055555555512d <Y+4>: push %rbp >> 0x000055555555512e <Y+5>: mov %rsp,%rbp >> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >> 0x0000555555555140 <Y+23>: cltq >> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >> 0x0000555555555155 <Y+44>: callq *%rax >> 0x000055555555516e <Z+0>: endbr64 >> 0x0000555555555172 <Z+4>: push %rbp >> 0x0000555555555173 <Z+5>: mov %rsp,%rbp >> 0x0000555555555176 <Z+8>: mov $0x1,%eax >> ... >> >> Note how X is called from Y+44 more than once with no branching or >> returns. >> > > Lets simply assume x86 architecture and Intel syntax. > > This is my latest revised infinite recursion halt deciding criteria: > > If the execution trace of function X() called by function Y() shows: > (1) Function X() is called twice in sequence from the same machine address of Y(). > (2) With the same parameters to X(). > (3) With no conditional branch or indexed jump instructions in Y(). > (4) With no function call returns from X(). > then the function call from Y() to X() is infinitely recursive unless > X() stops it. And you can't tell is the trace above meets those criteria? Oh well, you might be wrong and you'll never know it! I think a few minutes study of the trace would be worth it. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-17 20:43 -0500 |
| Message-ID | <v-WdnSUnevkhE-b9nZ2dnUU7-XWdnZ2d@giganews.com> |
| In reply to | #31292 |
On 4/17/2021 8:36 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 4/17/2021 7:34 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> If a function X() is called by function Y() twice in sequence from the >>>> same machine address of Y() with the same parameters to X() and the >>>> execution trace shows no conditional branch instructions in Y() or >>>> function call returns in X() then the function call from Y() to X() is >>>> infinitely recursive unless X() stops it. >>> >>> You mean like this: >>> >>> 0x000055555555517d <main+0>: endbr64 >>> 0x0000555555555181 <main+4>: push %rbp >>> 0x0000555555555182 <main+5>: mov %rsp,%rbp >>> 0x0000555555555185 <main+8>: callq 0x555555555129 <Y> >>> 0x0000555555555129 <Y+0>: endbr64 >>> 0x000055555555512d <Y+4>: push %rbp >>> 0x000055555555512e <Y+5>: mov %rsp,%rbp >>> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >>> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >>> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >>> 0x0000555555555140 <Y+23>: cltq >>> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >>> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >>> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >>> 0x0000555555555155 <Y+44>: callq *%rax >>> 0x000055555555515c <X+0>: endbr64 >>> 0x0000555555555160 <X+4>: push %rbp >>> 0x0000555555555161 <X+5>: mov %rsp,%rbp >>> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> >>> 0x0000555555555129 <Y+0>: endbr64 >>> 0x000055555555512d <Y+4>: push %rbp >>> 0x000055555555512e <Y+5>: mov %rsp,%rbp >>> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >>> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >>> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >>> 0x0000555555555140 <Y+23>: cltq >>> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >>> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >>> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >>> 0x0000555555555155 <Y+44>: callq *%rax >>> 0x000055555555515c <X+0>: endbr64 >>> 0x0000555555555160 <X+4>: push %rbp >>> 0x0000555555555161 <X+5>: mov %rsp,%rbp >>> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> >>> 0x0000555555555129 <Y+0>: endbr64 >>> 0x000055555555512d <Y+4>: push %rbp >>> 0x000055555555512e <Y+5>: mov %rsp,%rbp >>> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >>> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >>> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >>> 0x0000555555555140 <Y+23>: cltq >>> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >>> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >>> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >>> 0x0000555555555155 <Y+44>: callq *%rax >>> 0x000055555555515c <X+0>: endbr64 >>> 0x0000555555555160 <X+4>: push %rbp >>> 0x0000555555555161 <X+5>: mov %rsp,%rbp >>> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> >>> 0x0000555555555129 <Y+0>: endbr64 >>> 0x000055555555512d <Y+4>: push %rbp >>> 0x000055555555512e <Y+5>: mov %rsp,%rbp >>> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >>> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >>> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >>> 0x0000555555555140 <Y+23>: cltq >>> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >>> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >>> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >>> 0x0000555555555155 <Y+44>: callq *%rax >>> 0x000055555555515c <X+0>: endbr64 >>> 0x0000555555555160 <X+4>: push %rbp >>> 0x0000555555555161 <X+5>: mov %rsp,%rbp >>> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> >>> 0x0000555555555129 <Y+0>: endbr64 >>> 0x000055555555512d <Y+4>: push %rbp >>> 0x000055555555512e <Y+5>: mov %rsp,%rbp >>> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >>> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx >>> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >>> 0x0000555555555140 <Y+23>: cltq >>> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >>> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >>> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >>> 0x0000555555555155 <Y+44>: callq *%rax >>> 0x000055555555516e <Z+0>: endbr64 >>> 0x0000555555555172 <Z+4>: push %rbp >>> 0x0000555555555173 <Z+5>: mov %rsp,%rbp >>> 0x0000555555555176 <Z+8>: mov $0x1,%eax >>> ... >>> >>> Note how X is called from Y+44 more than once with no branching or >>> returns. >>> >> >> Lets simply assume x86 architecture and Intel syntax. >> >> This is my latest revised infinite recursion halt deciding criteria: >> >> If the execution trace of function X() called by function Y() shows: >> (1) Function X() is called twice in sequence from the same machine address of Y(). >> (2) With the same parameters to X(). >> (3) With no conditional branch or indexed jump instructions in Y(). >> (4) With no function call returns from X(). >> then the function call from Y() to X() is infinitely recursive unless >> X() stops it. > > And you can't tell is the trace above meets those criteria? Oh well, > you might be wrong and you'll never know it! I think a few minutes > study of the trace would be worth it. > I already did the relative rip addressing of x64 may allow some strange things that I can simply ignore by sticking with x86. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-18 13:21 -0500 |
| Message-ID | <RsGdncgeEM4B5eH9nZ2dnUU7-YPNnZ2d@giganews.com> |
| In reply to | #31281 |
On 4/17/2021 7:34 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> If a function X() is called by function Y() twice in sequence from the >> same machine address of Y() with the same parameters to X() and the >> execution trace shows no conditional branch instructions in Y() or >> function call returns in X() then the function call from Y() to X() is >> infinitely recursive unless X() stops it. > > You mean like this: > > 0x000055555555517d <main+0>: endbr64 > 0x0000555555555181 <main+4>: push %rbp > 0x0000555555555182 <main+5>: mov %rsp,%rbp > 0x0000555555555185 <main+8>: callq 0x555555555129 <Y> > 0x0000555555555129 <Y+0>: endbr64 > 0x000055555555512d <Y+4>: push %rbp > 0x000055555555512e <Y+5>: mov %rsp,%rbp > 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax > 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx It is this line-of-code that has the same effect as simulating a conditional branch using a jump table: > 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) > 0x0000555555555140 <Y+23>: cltq > 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx > 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax > 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax > 0x0000555555555155 <Y+44>: callq *%rax > 0x000055555555515c <X+0>: endbr64 > 0x0000555555555160 <X+4>: push %rbp > 0x0000555555555161 <X+5>: mov %rsp,%rbp > 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> Simply restricting the model to the x86 architecture gets rid of this problem. Since my purpose is to prove that there is at least one case where a halt decider can correctly decide that it was called in infinite recursion discarding an architectural model is a reasonable choice. This is the revised infinite recursion detection criteria: If the execution trace of function X() called by function Y() shows: (1) Function X() is called twice in sequence from the same machine address of Y(). (2) With the same parameters to X(). (3) With no conditional branch or indexed jump instructions in Y(). (4) With no function call returns from X(). then the function call from Y() to X() is infinitely recursive unless X() stops it. When X() detects that its simulation of Y() meets the above criteria then X() can definitely stop simulating Y() to prevent its own infinite execution. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-04-18 23:30 +0100 |
| Message-ID | <87sg3n444k.fsf@bsb.me.uk> |
| In reply to | #31345 |
olcott <NoOne@NoWhere.com> writes: > On 4/17/2021 7:34 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> If a function X() is called by function Y() twice in sequence from the >>> same machine address of Y() with the same parameters to X() and the >>> execution trace shows no conditional branch instructions in Y() or >>> function call returns in X() then the function call from Y() to X() is >>> infinitely recursive unless X() stops it. >> >> You mean like this: >> >> 0x000055555555517d <main+0>: endbr64 >> 0x0000555555555181 <main+4>: push %rbp >> 0x0000555555555182 <main+5>: mov %rsp,%rbp >> 0x0000555555555185 <main+8>: callq 0x555555555129 <Y> >> 0x0000555555555129 <Y+0>: endbr64 >> 0x000055555555512d <Y+4>: push %rbp >> 0x000055555555512e <Y+5>: mov %rsp,%rbp >> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax >> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx > > It is this line-of-code that has the same effect as simulating a > conditional branch using a jump table: >> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip) >> 0x0000555555555140 <Y+23>: cltq >> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx >> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax >> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax >> 0x0000555555555155 <Y+44>: callq *%rax >> 0x000055555555515c <X+0>: endbr64 >> 0x0000555555555160 <X+4>: push %rbp >> 0x0000555555555161 <X+5>: mov %rsp,%rbp >> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y> > > Simply restricting the model to the x86 architecture gets rid of this > problem. No. The fix is to write the correct criterion. > Since my purpose is to prove that there is at least one case where a > halt decider can correctly decide that it was called in infinite > recursion discarding an architectural model is a reasonable choice. That can't be your purpose because no sane person would doubt that that can be done. > This is the revised infinite recursion detection criteria: > > If the execution trace of function X() called by function Y() shows: > (1) Function X() is called twice in sequence from the same machine address of Y(). > (2) With the same parameters to X(). > (3) With no conditional branch or indexed jump instructions in Y(). > (4) With no function call returns from X(). > then the function call from Y() to X() is infinitely recursive unless > X() stops it. The other trace -- where you wanted another function called Simulate -- meets these criteria because the call through RAX is in another function. The trouble is not that this can't be done, but simply that you can't write the correct criteria. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-18 13:24 -0500 |
| Message-ID | <RsGdncseEM7e5OH9nZ2dnUU7-YOdnZ2d@giganews.com> |
| In reply to | #31239 |
On 4/18/2021 1:02 PM, wij wrote: > On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote: >> On 4/18/2021 9:52 AM, wij wrote: >>> On Saturday, 17 April 2021 at 22:18:02 UTC+8, olcott wrote: >>>> If a function X() is called by function Y() twice in sequence from the >>>> same machine address of Y() with the same parameters to X() and the >>>> execution trace shows no conditional branch instructions in Y() or >>>> function call returns in X() then the function call from Y() to X() is >>>> infinitely recursive unless X() stops it. >>>> >>>> The referenced execution trace is on x86 machine language, disassembled >>>> for human consumption. >>>> >>>> -- >>>> Copyright 2021 Pete Olcott >>>> >>>> "Great spirits have always encountered violent opposition from mediocre >>>> minds." Einstein >>> >>> I can think of no easy way to detect infinite recursion in C++. >>> >> The detection of the infinite recursion occurs at the machine language >> level. >>> From the problem description: >>> >>> Y: // no contiditonal branch >>> read_arg of Y >>> push_arg for X >>> call X >>> pop_arg for X >>> ret >>> >>> X: >>> ... // no return instruction >>> push_arg for Y >>> call Y >>> pop_arg for Y >>> ... // no return instruction, probably unreachable >>> >>> Obviously, both X() and Y() can never return. Then, what is the point? >>> >> The idea is to be able to define X() as a halt decider for functions >> that call X() in infinite recursion. > > Then, X() "You call it a halt decider", is defined not to return. When X() uses the following criteria to decide to stop simulating Y() then X() has correctly decided that Y() would otherwise cause X() to have infinite execution. If the execution trace of function X() called by function Y() shows: (1) Function X() is called twice in sequence from the same machine address of Y(). (2) With the same parameters to X(). (3) With no conditional branch or indexed jump instructions in Y(). (4) With no function call returns from X(). then the function call from Y() to X() is infinitely recursive unless X() stops it. > >> -- >> Copyright 2021 Pete Olcott >> >> "Great spirits have always encountered violent opposition from mediocre >> minds." Einstein -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mikko <mikko.levanto@outlook.com> |
|---|---|
| Date | 2021-04-19 19:43 +0300 |
| Message-ID | <mikko.levanto-0211E1.19433119042021@news.eternal-september.org> |
| In reply to | #31239 |
In article <HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com>, olcott <NoOne@NoWhere.com> wrote: > If a function X() is called by function Y() twice in sequence from the > same machine address of Y() with the same parameters to X() and the > execution trace shows no conditional branch instructions in Y() or > function call returns in X() then the function call from Y() to X() is > infinitely recursive unless X() stops it. Those criteria demand more than is needed but also fail to mention some necessary criteria (perhaps one could regard them self evident). The criteria don't apply if there is a possibility of interrupts or concurrent execution so that executions may interfere. Without such possibility X cannot stop execution of a subroutine it calls. If there are no conditional branches then it does not matter whether the parameters are the same -- the recursion is infinite anyway. If there are conditional branches the recursion is infinite if the parameters and global and static variables that affect the branch conditions must be the same or at least always determine the same branch. The parameters and variables that do no affect the branches need not be the same. Mikko
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-19 11:53 -0500 |
| Message-ID | <_MGdnW9xkusEKOD9nZ2dnUU7-IUAAAAA@giganews.com> |
| In reply to | #31462 |
On 4/19/2021 11:43 AM, Mikko wrote:
> In article <HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com>,
> olcott <NoOne@NoWhere.com> wrote:
>
>> If a function X() is called by function Y() twice in sequence from the
>> same machine address of Y() with the same parameters to X() and the
>> execution trace shows no conditional branch instructions in Y() or
>> function call returns in X() then the function call from Y() to X() is
>> infinitely recursive unless X() stops it.
>
> Those criteria demand more than is needed but also fail to mention some
> necessary criteria (perhaps one could regard them self evident).
>
> The criteria don't apply if there is a possibility of interrupts or
> concurrent execution so that executions may interfere. Without such
> possibility X cannot stop execution of a subroutine it calls.
>
Infinite recursion detection criteria:
(1) Function X() is called twice in sequence from the same machine
address of Y().
(2) With the same parameters to X().
(3) With no conditional branch or indexed jump instructions in Y().
(4) With no function call returns from X().
The following code (including an x86 emulator) is written in "C"
void X(u32 P, u32 I)
{
Simulate(P, I);
}
void Y(u32 P)
{
X(P, P);
}
int main()
{
X((u32)Y, (u32)Y);
}
When X() simulates the x86 machine language of Y() and examines
resulting execution trace after simulating each machine instruction of
Y() then X() can apply the criteria provided above to correctly decide
to stop simulating Y() on the basis that Y() would otherwise cause X()
have infinite execution.
Whenever the above criteria is met then X() must stop simulating Y() to
prevent its own infinite execution.
> If there are no conditional branches then it does not matter whether the
> parameters are the same -- the recursion is infinite anyway.
No conditional branches in Y(), there are conditional branches in X(),
they are ignored.
> If there are
> conditional branches the recursion is infinite if the parameters and
> global and static variables that affect the branch conditions must be
> the same or at least always determine the same branch. The parameters
> and variables that do no affect the branches need not be the same.
>
> Mikko
>
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-04-19 13:47 -0400 |
| Message-ID | <GmjfI.9091$AU5.7391@fx29.iad> |
| In reply to | #31463 |
On 4/19/21 12:53 PM, olcott wrote:
> On 4/19/2021 11:43 AM, Mikko wrote:
>> In article <HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com>,
>> olcott <NoOne@NoWhere.com> wrote:
>>
>>> If a function X() is called by function Y() twice in sequence from the
>>> same machine address of Y() with the same parameters to X() and the
>>> execution trace shows no conditional branch instructions in Y() or
>>> function call returns in X() then the function call from Y() to X() is
>>> infinitely recursive unless X() stops it.
>>
>> Those criteria demand more than is needed but also fail to mention some
>> necessary criteria (perhaps one could regard them self evident).
>>
>> The criteria don't apply if there is a possibility of interrupts or
>> concurrent execution so that executions may interfere. Without such
>> possibility X cannot stop execution of a subroutine it calls.
>>
>
> Infinite recursion detection criteria:
> (1) Function X() is called twice in sequence from the same machine
> address of Y().
> (2) With the same parameters to X().
> (3) With no conditional branch or indexed jump instructions in Y().
> (4) With no function call returns from X().
>
> The following code (including an x86 emulator) is written in "C"
>
> void X(u32 P, u32 I)
> {
> Simulate(P, I);
> }
>
> void Y(u32 P)
> {
> X(P, P);
> }
>
> int main()
> {
> X((u32)Y, (u32)Y);
> }
>
> When X() simulates the x86 machine language of Y() and examines
> resulting execution trace after simulating each machine instruction of
> Y() then X() can apply the criteria provided above to correctly decide
> to stop simulating Y() on the basis that Y() would otherwise cause X()
> have infinite execution.
Except that the defined X() does none of this.
>
> Whenever the above criteria is met then X() must stop simulating Y() to
> prevent its own infinite execution.
>
Which it can't do as written, since X() is JUST a call to the simulator.
>> If there are no conditional branches then it does not matter whether the
>> parameters are the same -- the recursion is infinite anyway.
>
> No conditional branches in Y(), there are conditional branches in X(),
> they are ignored.
>
>> If there are
>> conditional branches the recursion is infinite if the parameters and
>> global and static variables that affect the branch conditions must be
>> the same or at least always determine the same branch. The parameters
>> and variables that do no affect the branches need not be the same.
>>
>> Mikko
>>
>
>
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | comp.theory
csiph-web