# Stackoverflow in Rekursion. Bin ich schuld oder Java?



## Patrick_GAST (29. Nov 2007)

Hallo

ich arbeite gerade an einem Programm das zum auffinden von Sicherheitslücken im lokalen Netz und Webanwendungen dienen soll, in diesem Projekt habe eine Klasse BruteForce, mit einer rekursiven Methode, geschrieben um schwache Passwörter aufzuspüren, hierfür verwende ich die Ascii Tabelle von '!' bis '~'. Um es nicht zu performancelastig zu gestallten arbeite ich mit char Arrays und nicht mit Listen oder dergleichen.

Leider führt es immer wieder zu StackOverflows, nachdem ich den gc an so ziemlich jeder Stelle manuel aufgerufen haben ist es ein wenig weiter gelaufen aber das reicht nicht, gibt es Programmiermethoden um dieses Problem zu umgehen?


Hier der Code:


```
public class BruteForce {

	private String toCompare = "!";
	private char[] array;
	private boolean geschafft = false;
	
	public BruteForce() 
	{
		array = toCompare.toCharArray();
	}
	
	//Erzeugt neues Array und kopiert die Werte des Alten
	//zusätzlich wird im letzten Feld noch der Initialwert gesetzt 
	private char[] increaseArraySize(char[] zeichen)
	{
		char[] newCharSequenze = new char[zeichen.length + 1];
		int index = 0;
		for(; index < zeichen.length; index++)
		{
			newCharSequenze[index] = zeichen[index];
		}
		newCharSequenze[index] = 0x21;
		zeichen = null;
		System.gc();
		
		return newCharSequenze;
	}
	
	//Ausgabe Funktion
	private void ausgabe()
	{
		System.gc();
		for(int count = 0; count < array.length; count++)
		{
			System.out.print(array[count]);
		}
		System.out.println();
	}
	
	//rekursive methode um alle Fälle durchzugehen bis geschafft
	private void increase(int index)
	{
		if(!geschafft)
		{
			System.gc();
			//falls der übergeben Index im array vorkommt 
			if(index < array.length)
			{
				ausgabe();
				compare();
				//wird der Wert um +1 erhöht
				array[index]++;
				//falls dieser Wert dann größer ist als 0x7E also '~'
				if(array[index] > 0x7E)
				{
					System.out.println("greater then");
					//wird der Wert wieder auf den Startwert gesetzt 
					array[index] = 0x21;
					//und increase wird mit dem nächst höheren index aufgerufen
					increase(index+1);
				}
				//falls der Wert kleiner als 0x7E ist 
				else
				{
					//wird increase mit Startindex aufgerufen
					increase(0);
				}
			}
			//falls der übergebene index nicht im array vorkommt
			else
			{
				System.out.println("erweitere Array");
				//wird das Array erweitert
				array = increaseArraySize(array);
				//und increase mit Startindex aufgerufen
				increase(0);
			}
		}
	}
	
	//Vergleichsfunktion
	private void compare()
	{
		toCompare = new String(array);
		System.gc();
		if(toCompare.equals("TEST"))
		{
			geschafft = true;
			System.out.println("GESCHAFFT!!!");
		}
	}
	
	public void start()
	{
		increase(0);
	}
}
```


Ist noch teilweise einbischen unschön aber ist ja auch noch prealpha   
Liegt das jetzt an Java oder hab ich Mist programmiert... oder beides ???:L

Schönen Tag noch


----------



## Wildcard (29. Nov 2007)

Mit dem GC hat das überhaupt nichts zu tun.
Es gibt in jeder Programmiersprache Speicher für den Stack auf dem Variablen und Rücksprungadressen abgelegt werden.
Wenn die Rekursion zu tief geht, läuft dieser Speicher voll was zu genannter Exception führt.
Die beiden Lösungsmöglichkeiten sind:
-Vergrößerung des Stacks
-Iterative Programmierung

Als Tipp:
Ein rekursiver Brute Force Angriff ist dämlich...


----------



## maki (29. Nov 2007)

> Liegt das jetzt an Java oder hab ich Mist programmiert... oder beides icon_scratch.gif


Rekursion führt zu einem Funktionsaufruf in jedem Durchlauf, da wird der Stack bei vielen Aufrufen knapp.

Iteration (Schleifen) haben dieses Problem nicht, die Stack Klasse ist nützlich in solchen Fällen.


----------



## SlaterB (29. Nov 2007)

StackOverflow heißt StackOverflow und nicht OutOfMemoryException, was soll der Gc da machen, den Stack löschen? 
nagut, mit weniger Heap hätte der Stack wieder mehr Platz, falls der auch den Heap benutzt (?)
aber so eine Exception kommt doch nochmalerweise bei einer Endlos- oder zumindest zu fahrlässigen Rekursion,
da bringt es dir auch kaum etwas, den Stack höchstens zu verdoppeln

-------

> toCompare = new String(array); 
> System.gc(); 
> if(toCompare.equals("TEST")) 

ist das nur testweise? wenn diese compare-Funktion tausendfach aufgerufen wird,
dann vergleiche doch das Array mit dem String Zeichen für Zeichen,
ohne unnötig einen String zu erzeugen und mit GC aufzuräumen versuchen

--------

dein Hauptprogramm mit der Rekursion habe ich persönlich noch nicht verstanden,
willst du da keine minimale Erklärung abgegben?
'macht xy, in jedem Rekursionsschritt yz'

und wie wärs mit einer main-Operation + Test-Eingaben, um das ganz ablaufen zu lassen bis zur Exception?


----------



## Patrick_GAST (29. Nov 2007)

Das Programm beginnt bei '!' alle Zeichen bis '~' durchzuiterieren, falls nichts gefudnen wird, wird noch ein Zeichen angehängt und es geht von vorne los usw.


Meine Main:


```
public static void main(String[] args) {

		BruteForce brute = new BruteForce();
		brute.start();
	}
```

und hier die Ausgabe auch wenn das nicht viel bringt denke ich:

nopaste.com/p/atvhnQcEb

ich werd mich mal daran machen das ganz iteratiev zu lösen, für weitere Hilfe bin ich trotzdem dankbar.


----------



## SlaterB (29. Nov 2007)

im Grunde brauchst du statt der Rekursion nur eine Schleife,

int index = 0;
while(!geschafft) {
..
index erhöhen
...
}


----------



## patrick_GAST (29. Nov 2007)

Jo danke, ich weiß    jetzt 

Ist es demnach nicht möglich tiefe rekursionen zu implementieren?


----------



## The_S (29. Nov 2007)

doch, aber alles hat seine Grenzen.


----------



## Marco13 (29. Nov 2007)

Zwischen den Zeichen ! und ~ liegen 93 Zeichen. Bei einem Passwort der Länge 5 hat man damit eine Rekursionstiefe von 6.9 Milliarden... Naja, ganz so weit wird er nicht kommen: Stell' dir nur mal vor, für jeden Rekursionsstufe würden nur 10 bytes Stack-Speicher benötigt (es dürften aber _deutlich_ mehr sein) - dann wären das schon kanpp 70 GB für ein Furz-Passwort, das man iterativ in ein paar Minuten bei wenigen KB Speicherbedarf durchratten lassen könnte....


----------



## happy_robot (29. Nov 2007)

> Stackoverflow in Rekursion. Bin ich schuld oder Java?



Du


----------

