Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #31298

Re: Infinite recursion detection criteria (Please correct me if I am wrong)

Subject Re: Infinite recursion detection criteria (Please correct me if I am wrong)
Newsgroups comp.theory
References (1 earlier) <87y2dg8m7i.fsf@bsb.me.uk> <tLKdnTL0L96r4ub9nZ2dnUU7-d-dnZ2d@giganews.com> <87czus8kdr.fsf@bsb.me.uk> <kvqdnQAdt47ZFub9nZ2dnUU7-efNnZ2d@giganews.com> <87k0p07467.fsf@bsb.me.uk>
From olcott <NoOne@NoWhere.com>
Date 2021-04-17 21:01 -0500
Message-ID <QaSdnZSATouWDub9nZ2dnUU7-R2dnZ2d@giganews.com> (permalink)

Show all headers | View raw


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

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

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

csiph-web