Theorie: Rekursive Funktion Abbrechen und Fortsetzen

[alzaimar]

Wie speichert man den Stack?

[Der_Unwissende]

Ich glaube immernoch, dass du dir gar nicht den ganzen Stack merken musst. Bei einem Bruteforce musst du doch über irgendeine Struktur iterieren (z.B. ein Wörterbuch, ein Eingabealphabet oder eine Zahl oder oder oder). Dahinter steckt doch aber eine Struktur.
O.b.d.A. nehmen wir mal an du benutzt ein Wort. Also musst du dir doch eigentlich nur merken, welches Wort gerade dran ist. Der Nachfolger für dieses Wort dürfte eindeutig sein. Alle Vorgänger scheiden aus, denn sie waren ja falsch. Dann musst du dir nicht die Mühe machen den Stack zu sichern.
Deshalb denke ich aber auch, dass du das ganze gleich iterativ lösen (erspart dir dann die gesamten Rücksprünge). Kann natürlich sein, dass dein Algorithmus nicht Endrekursiv ist (hatten wir ja schon), dann kannst du es nicht so leicht so gestalten. Aber ich denke, du kannst die Rekursion dann auch leicht umwandeln (in Endrekursion) und es dir dann merken. Hängt aber natürlich davon ab, wie dein Algorithmus aussieht.

[alzaimar]

Ist der Algorithmus geheim? Vielleicht können wir ihn ja iterativ umformulieren?

[ripper8472]

bruteforce, also "raufzaehlen" kann man doch ganz einfach fortsetzen. dazu braucht man nur eine increment() funktion, die auf eine "zahl" eben was draufzaehlt. rekursion gibts da nichtmal in der increment() funktion.

[tommie-lie]

Zitat von ripper8472:

bruteforce, also "raufzaehlen" kann man doch ganz einfach fortsetzen.

Je nach Angriffsmethode ist BruteForce nicht immer nur stupides hochzählen. Denk' zum Beispiel mal an das Knacken eines Labyrinths per BruteForce, bei dem man das Labyrinth in einzelne Labyrinthe unterteilt und rekursiv den gleichen Algorithmus aufruft, bis man entweder in einer Sackgasse landet oder am Ausgang. In dem Fall könnte ich mir zwar Knotenpunkte merken, an denen ich schon war, aber dadurch wird der Algorithmus ungemein komplizierter, weil ich nicht mehr nach einem einfachen Schema das Labyrinth durchsuchen kann.

[Vjay]

@alzaimar

Ich gebe dir völlig Recht in deiner Behauptung dass jede rekursive Funktion in eine iterative umgewandelt werden könnte - da der Compiler ja nichts anderes macht.

Auch wenn der Bruteforce-Algo sicherlich in eine iterative Funktion umgebaut werden könnte, würde mich trotzdem die ursprüngliche Fragestellung interessieren.

Denn auch wenn man jede nun iterative Funktion mit Unterbrechungs- und Wiedereinstiegsfunktionen versehen könnte, wäre es unter umständen sehr viel einfacher wenn man einen Thread suspenden und seinen gesamten Stack sichern und wiederherstellen könnte. Okay das wird sicher auch alles andere als einfach aber interessieren würde es mich schon sehr. Und wenn hier jemand dafür etwas aus dem Hut zaubern könnte wäre ich davon, auch wenn ich es wahrscheinlich nie verwenden werde, ziemlich begeistert .

[alzaimar]

Das wirklich sehr weit ausgeholt mit der Theorie über Transformationen, zurück zum Thema:
Soweit ich das weiss (von Tommie-lie), geht das so nicht, d.h. man kann den Stack zwar sichern, aber wiederherstellen ist nich, das erlaubt XP nicht. Ausser, du schreibst Dir einen Treiber.

[tommie-lie]

Zitat von alzaimar:

das erlaubt XP nicht

Genau genommen (und wir wollen ja pingelig sein ) erlaubt es der Prozessor nicht, der verweigert nämlich den Zugriff auf die GDT, wenn man selbst nicht im Ring 0 läuft, und ein vernünftiges Betriebssystem würde Anwendungen never ever im Ring 0 laufen lassen (Für Anwendungen gilt allgemein: Ring 3 oder gar nicht ).

[alzaimar]

Zitat von tommie-lie:

Zitat von alzaimar:

das erlaubt XP nicht

Genau genommen (und wir wollen ja pingelig sein ) erlaubt es der Prozessor nicht...im Ring 0 läuft, und ein vernünftiges Betriebssystem ...

Da werd ich pingeligtechnisch noch mal nachhaken: Ist 'Ring 0' eine Eigenschaft eines "vernünftigen Betriebssystems", oder der CPU?

[tommie-lie]

Zitat von alzaimar:

Ist 'Ring 0' eine Eigenschaft eines "vernünftigen Betriebssystems", oder der CPU?

Der CPU. Moderne Intel-Prozessoren (IIRC 80286 und aufwärts, vielleicht auch erst ab 80386) haben für ihren Protected Mode sogenannte Ringe, 4 an der Zahl. Ring 0 ist vom dunklen Herrscher über dem Feuerberg geschmiedet worden, deswegen hat der auch die meisten Privilegien. Den dritten Ring bekamen die ollen Zwergenkönige, der hat die wenigsten Privilegien.
Im Protected Mode befinden sich in den Segmentregistern keine echten Adressen mehr, sondern Segmentselektoren, die auf einen Eintrag in der Deskriptortabelle zeigen. So ein Selektor besteht aus dem Index, 'nem Verweis ob es die Local oder die Global Descriptor Table (LDT, GDT) geht, und zwei Bits für das Requested Privilege Level. Ein Programm darf nur auf ein Segment zugreifen, wenn das RPL des Codesegmentes (aktuelles Privilege Level) kleiner oder gleich dem RPL des Zielsegmentes ist. Läuft mein Code im Ring 3 weil das Codesegment ein RPL von 3 hat, dann kann ich nur auf Datensegmente zugreifen, die ebenfalls 3 sind. Läuft mein Code hingegen im Ring 2, darf ich auf Segmente in Ring 2 und 3 zugreifen. In einem Segmentdeskriptor gibt es ebenfalls ein Descriptor Privilege Level, durch das gewährleistet wird, daß wirklich nur Prozesse im richtigen Ring auf einen Deskriptor zugreifen können.
Die gesamte Prüfung rund um Privilege Levels wird von der Adressierungslogik des Prozessors durchgeführt (im Fehlerfalls gibt's deswegen 'ne Hardwareexception (der allseits beliebte Protection Fault oder Schutzverletzung)) und hat mit dem Betriebssystem nichts zu tun.