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


Groups > comp.theory > #31295

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

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Infinite recursion detection criteria (Please correct me if I am wrong)
Date 2021-04-18 02:49 +0100
Organization A noiseless patient Spider
Message-ID <87k0p07467.fsf@bsb.me.uk> (permalink)
References <HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com> <87y2dg8m7i.fsf@bsb.me.uk> <tLKdnTL0L96r4ub9nZ2dnUU7-d-dnZ2d@giganews.com> <87czus8kdr.fsf@bsb.me.uk> <kvqdnQAdt47ZFub9nZ2dnUU7-efNnZ2d@giganews.com>

Show all headers | View raw


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.

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