Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Real Programmers don't eat quiche. They eat Twinkies and Szechwan food.


devel / comp.lang.c++ / Termination Analyzer H prevents Denial of Service attacks

SubjectAuthor
o Termination Analyzer H prevents Denial of Service attacksolcott

1
Termination Analyzer H prevents Denial of Service attacks

<u6ank0$3ng51$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=333&group=comp.lang.c%2B%2B#333

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.lang.c++
Subject: Termination Analyzer H prevents Denial of Service attacks
Date: Tue, 13 Jun 2023 16:38:08 -0500
Organization: A noiseless patient Spider
Lines: 57
Message-ID: <u6ank0$3ng51$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 13 Jun 2023 21:38:08 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="2fe57491806f1f51a6ef139fb1ef3bc2";
logging-data="3915937"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+Ciogm1JEqOQvhpmEYqBmi"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.11.2
Cancel-Lock: sha1:YTi2gkJKd0JXrp1nQ1yuMfo+jAA=
Content-Language: en-US
 by: olcott - Tue, 13 Jun 2023 21:38 UTC

When termination analyzer H is intended to prevent denial of service
attacks is presented with an input D that has been defined to have a
pathological relationship to this termination analyzer, it correctly
aborts the simulation of this input that would have otherwise caused H
to never terminate until system resources have been exhausted, crashing
the system.

Can D correctly simulated by H terminate normally?

The x86utm operating system based on an open source x86 emulator. This
system enables one C function to execute another C function in debug
step mode. When H simulates D it creates a separate process context for
D with its own memory, stack and virtual registers. H is able to
simulate D simulating itself, thus the only limit to recursive
simulations is RAM.

// The following is written in C
//
01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }

Execution Trace
Line 14: main() invokes H(D,D);

keeps repeating (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)

Simulation invariant:
D correctly simulated by H cannot possibly reach its own line 09.

H correctly determines that D correctly simulated by H cannot possibly
terminate normally on the basis that H recognizes a dynamic behavior
pattern equivalent to infinite recursion.

The x86utm operating system (includes several termination analyzers)
https://github.com/plolcott/x86utm

It compiles with the 2017 version of the Community Edition
https://visualstudio.microsoft.com/thank-you-downloading-visual-studio/?sku=Community&rel=15

--
Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer


devel / comp.lang.c++ / Termination Analyzer H prevents Denial of Service attacks

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor