TBruteForce - Version 0.5a [Update: 28.04.2008]

[Meflin]

TBruteForce
Wer hätt's gedacht - eine Brute Force Klasse für Delphi

Aktuelle Version: 0.5a
Download: im Anhang [6,39 KB]

Was ist TBruteForce?

TBruteForce ist eine Klasse, mit der die Implementierung einer BruteForcing-Funktion im eigenen Programm möglichst einfach und gleichzeitig möglichst universell ermöglicht werden soll. Die aktuelle Version verbraucht an sich kaum Arbeitsspeicher (es sei denn der Programmierer entscheidet sich dazu, die erzeugten Kombinationen in irgendeiner Form zwischenzuspeichern). Das bedeutet, dass für die Performance des Vorgangs (abgesehen von der Effektivität des Codes) allein die Prozessorgeschwindigkeit verantwortlich ist.
Bei einem 2GHz Prozessor(kern) liegt die blose Geschwindigkeit bei etwa 50.000.000 Kombinationen pro Sekunde, durch das Zusammensetzen der strings zur Ausgabe verringert sich die Geschwindigkeit auf etwa 2.000.000 Kombinationen pro Sekunde (hier besteht eindeutig Optimierungsbedarf ). Lässt man sich jetzt noch alle Kombinationen sichtbar ausgeben, beispielsweise in einer Konsole, so verringert sich die Geschwindigkeit weiter auf ca. 20.000 Kombinationen pro Sekunde.
So, ich hoffe nun hast Du eine ungefähre Vorstellung in welchen Geschwindigkeitsbereichen man sich mit der Klasse theoretisch und in der Praxis bewegen kann.

Verwendung

Um die Klasse in Betrieb zu nehmen, ist nichts weiter nötig, als die Unit BruteForce.pas in das Projektverzeichnis zu kopieren und in die uses der fraglichen Unit aufzunehmen.

Delphi-Quellcode:

uses
  BruteForce;

Um mit einem einfachen Beispiel zu beginnen: Wir wollen Kombinationen mit 5 Zeichen Länge erzeugen, der Zeichenvorrat soll dabei das Alphabet in Kleinbuchstaben sein. Oder anders ausgedrückt wir wollen alle Kombinationen von aaaaa, aaaab, aaaac, ... bis zzzzx, zzzzy, zzzzz bilden.

Delphi-Quellcode:

var
  BruteForce: TBruteForce;
begin
  // Instanzierung
  BruteForce := TBruteForce.Create;

  // Wir wollen 5 Stellen kombinieren, sg. "Nodes"
  BruteForce.NodeCount := 5;

  // Zeichenvorrat setzen, AlphaLowerCase ist eine Konstante die von der Unit bereitgestellt wird
  // Als ElementList erwartet die Klasse ein array of string. BFConstToDynArray wandelt ein 
  // statisches array of string in ein dynamisches array of string um.
  BruteForce.ElementList := BFConstToDynArray(AlphaLowerCase);

  // Soderle. Bereits jetzt enthält BruteForce.Value die erste Kombinationen, in diesem Fall aaaaa.
  // Also müssen wir die gleich ausgeben.
  DoSomething(BruteForce.Value);

  // Jetzt gehts ans eigentliche BruteForcen, wir bilden die Kombinationen
  // BruteForce.NextValue bildet die nächste Kombinationen und gibt das Ergebnis als string zurück
  while not BruteForce.Finished do begin
    DoSomething(BruteForce.NextValue);
  end;

  // Wuppdi - jetzt sind wir schon fertig ;)

Wie viele Kombinationen die Klasse erzeugen wird lässt sich über
BruteForce.ToDo auslesen.


Jetzt ist es aber so, dass man jedem Node seinen eigenen Zeichenvorrat zuweisen kann. D.h. wir könnten beispielsweise auch Kombinationen der länge 5 erzeugen, bei denen die letzten beiden Zeichen Ziffern sind. Das ginge so:

Delphi-Quellcode:

var
  BruteForce: TBruteForce;
begin
  BruteForce := TBruteForce.Create;
  BruteForce.NodeCount := 5;
  BruteForce.ElementList := BFConstToDynArray(AlphaLowerCase);
  // Jetzt kommts ;)
  BruteForce.Nodes[0].ElementList := BFConstToDynArray(Numeric);
  BruteForce.Nodes[1].ElementList := BFConstToDynArray(Numeric);

  DoSomething(BruteForce.Value);

  while not BruteForce.Finished do begin
    DoSomething(BruteForce.NextValue);
  end;

Dieser Code würde alle Kombinationen von aaa00, aaa01,... bis zzz99 ausgeben. Jetzt wunderst Du dich vielleicht, wieso wir den Zeichenvorrat der Nodes 0 und 1 ändern und nicht den der Nodes 3 und 4 (die Zahlen sollen ja rechts hin). Nunja, je weiter ein Node links steht, desto höherwertiger ist er. Deshalb wird der Node, der in der Ausgabe die "rechteste" Stelle repräsentiert über den Index 0 angesprochen. Puh, ich hoffe das ist einigermasen verständlich

Code:

Wort a a a 0 0
Node 4 3 2 1 0

To Do

Bei der Version 0.5a handelt es sich um ein experimentelles Release. Es sind noch kaum Fehlerbehandlungsroutinen eingebaut! Bis jetzt ist es auch so, dass NodeCount unbedingt vor ElementList gesetzt werden muss (ein Henne-Ei-Problem für das ich bis jetzt keine überzeugende Lösung gefunden habe).
Einbauen will ich noch eine Speichern/Laden Funktion, die Möglichkeit, den BruteForce-Vorgang in beliebig viele Pakete aufzuteilen (Multithreading, Parallel Computing), sowie eine Ausgabe der Kombinationen wahlweise als array of string (bzw. TBFElementList). Ich habe auch schon mit dem Gedanken gespielt, beliebige Dinge kombinierbar zu machen (beispielsweise Integer, Objekte, etc). Aber ich bin mir nicht sicher, ob sich der Aufwand lohnen würde.

Ich würde mich freuen, wenn von euch noch Vorschläge und Anregungen kämen, wie man die Komponente noch erweitern könnte

Changelog

Code:

28.04.2008: Version 0.5a "Pandora" released
     Neu: 100% Codebasis ;)
     Kein Multithreading mehr integriert
     Es ist keine Komponente mehr

09.05.2006: Version 0.3b und aktualisierte Demo released
     Neu: Wahl zwischen iterativem und rekurivem Algorithmus
     Neu: TMaxThreads property
     Neu: OnThreadStart Event
     Neu: KeyList jetzt direkt in TBruteForce implementiert, keine 2 Komponenten mehr
     TThreadStatus nicht mehr hardgecodet
     Und alles, was ich inzwischen vergessen habe :(

05.10.2005: Version 0.1.3 Beta RC 2 und aktualisierte Demo released
     Minibugfix beim OnProgressChangeEvent gefixt

03.10.2005: Version 0.1.3 Beta RC 1 und aktualisierte Demo released
     Bugfix: Komponente zählt jetzt richtig
     Bugfix: Memory Leak entfernt
     Performance: Callback Funktion OnProgressChange geht jetzt nicht mehr so auf die Performance

30.08.2005: Version 0.1.2 Beta und aktualisierte Demo released
     Bugfix: das Problem, das das OnLastThreadFinished Event öfter ausgeführt wird sollte behoben sein
     Bugfix: Kleine Unsauberheit beim Progresscounter behoben
     Bugfix: OnProgressChangeTolerance war etwas zu tolerant
     Neu: eine Exception wurde ergänzt

29.08.2005: Demo released

27.08.2005: Version 0.1.1 Beta und neue Demo released
     Bugfix: bei EndLength = 1 werden jetzt nicht mehr fälschlicherweise die 2-stelligen Keys erzeugt
     Neu: Event OnProgressChange
     Neu: public property OnProgressChangeTolerance
     Neu: Exception Handling

26.08.2005: Demo released

25.08.2005: Version 0.1 Beta released

[Larsi]

ich hab delphi 2005 personal, hab dadpackage auch installiert und so aber beim ausführen will delphi immer irgendeine bruteforce.dcu datei oder so haben weil die in der uses liste steht!

[Larsi]

kann mir da keiner helfen; was mach ich falsch???

[o0o]

wenn du alles installiert hast gib bei deiner windows suche "bruteforce.dcu" ein und den pfad dieser datei den du dann finden wirst fuegst du der library hinzu

das wars

o0o

[Meflin]

Zitat von mOfl:

Tut sie? Hm, irgendwie verstehe ich die Komponente nicht... wo kann ich denn auf das aktuelle Element zugreifen?

Tut sie. Ich kann dir jetzt aus dem Stegreif nicht weiterhelfen (ist doch schon ein Weilchen her dass ich die Komponente geschrieben habe) aber ich werde mir daheim nochmal die Sourcen zu Gemüte führen und mich dann hier nochmal melden

Zitat:

kann mir da keiner helfen; was mach ich falsch???

Du musst das Package kompilieren und das Verzeichnis zu deinem Bibliothekspfad hinzufügen.

[Meflin]

Es ist soweit. Hier kommt die komplett überarbeitete neue Version...

28.04.2008: Version 0.5a "Pandora" released

Diese neue Version hat absolut nichts mehr mit der Version 0.3b gemeinsam - sprich alle Beiträge in diesem thread vor diesem sind hiermit hinfällig Ich habe die Klasse von Grund auf neu programmiert!

Download: im Anhang [6,39 KB]

Über TBruteForce

Die aktuelle Version verbraucht an sich kaum Arbeitsspeicher (es sei denn der Programmierer entscheidet sich dazu, die erzeugten Kombinationen in irgendeiner Form zwischenzuspeichern). Das bedeutet, dass für die Performance des Vorgangs (abgesehen von der Effektivität des Codes) allein die Prozessorgeschwindigkeit verantwortlich ist.
Bei einem 2GHz Prozessor(kern) liegt die blose Geschwindigkeit bei etwa 50.000.000 Kombinationen pro Sekunde, durch das Zusammensetzen der strings zur Ausgabe verringert sich die Geschwindigkeit auf etwa 2.000.000 Kombinationen pro Sekunde (hier besteht eindeutig Optimierungsbedarf ). Lässt man sich jetzt noch alle Kombinationen sichtbar ausgeben, beispielsweise in einer Konsole, so verringert sich die Geschwindigkeit weiter auf ca. 20.000 Kombinationen pro Sekunde.
So, ich hoffe nun hast Du eine ungefähre Vorstellung in welchen Geschwindigkeitsbereichen man sich mit der Klasse theoretisch und in der Praxis bewegen kann.

Verwendung

Um die Klasse in Betrieb zu nehmen, ist nichts weiter nötig, als die Unit BruteForce.pas in das Projektverzeichnis zu kopieren und in die uses der fraglichen Unit aufzunehmen.

Delphi-Quellcode:

uses
  BruteForce;

Um mit einem einfachen Beispiel zu beginnen: Wir wollen Kombinationen mit 5 Zeichen Länge erzeugen, der Zeichenvorrat soll dabei das Alphabet in Kleinbuchstaben sein. Oder anders ausgedrückt wir wollen alle Kombinationen von aaaaa, aaaab, aaaac, ... bis zzzzx, zzzzy, zzzzz bilden.

Delphi-Quellcode:

var
  BruteForce: TBruteForce;
begin
  // Instanzierung
  BruteForce := TBruteForce.Create;

  // Wir wollen 5 Stellen kombinieren, sg. "Nodes"
  BruteForce.NodeCount := 5;

  // Zeichenvorrat setzen, AlphaLowerCase ist eine Konstante die von der Unit bereitgestellt wird
  // Als ElementList erwartet die Klasse ein array of string. BFConstToDynArray wandelt ein 
  // statisches array of string in ein dynamisches array of string um.
  BruteForce.ElementList := BFConstToDynArray(AlphaLowerCase);

  // Soderle. Bereits jetzt enthält BruteForce.Value die erste Kombinationen, in diesem Fall aaaaa.
  // Also müssen wir die gleich ausgeben.
  DoSomething(BruteForce.Value);

  // Jetzt gehts ans eigentliche BruteForcen, wir bilden die Kombinationen
  // BruteForce.NextValue bildet die nächste Kombinationen und gibt das Ergebnis als string zurück
  while not BruteForce.Finished do begin
    DoSomething(BruteForce.NextValue);
  end;

  // Wuppdi - jetzt sind wir schon fertig ;)

Wie viele Kombinationen die Klasse erzeugen wird lässt sich über
BruteForce.ToDo auslesen.


Jetzt ist es aber so, dass man jedem Node seinen eigenen Zeichenvorrat zuweisen kann. D.h. wir könnten beispielsweise auch Kombinationen der länge 5 erzeugen, bei denen die letzten beiden Zeichen Ziffern sind. Das ginge so:

Delphi-Quellcode:

var
  BruteForce: TBruteForce;
begin
  BruteForce := TBruteForce.Create;
  BruteForce.NodeCount := 5;
  BruteForce.ElementList := BFConstToDynArray(AlphaLowerCase);
  // Jetzt kommts ;)
  BruteForce.Nodes[0].ElementList := BFConstToDynArray(Numeric);
  BruteForce.Nodes[1].ElementList := BFConstToDynArray(Numeric);

  DoSomething(BruteForce.Value);

  while not BruteForce.Finished do begin
    DoSomething(BruteForce.NextValue);
  end;

Dieser Code würde alle Kombinationen von aaa00, aaa01,... bis zzz99 ausgeben. Jetzt wunderst Du dich vielleicht, wieso wir den Zeichenvorrat der Nodes 0 und 1 ändern und nicht den der Nodes 3 und 4 (die Zahlen sollen ja rechts hin). Nunja, je weiter ein Node links steht, desto höherwertiger ist er. Deshalb wird der Node, der in der Ausgabe die "rechteste" Stelle repräsentiert über den Index 0 angesprochen. Puh, ich hoffe das ist einigermasen verständlich

Code:

Wort a a a 0 0
Node 4 3 2 1 0

To Do

Bei der Version 0.5a handelt es sich um ein experimentelles Release. Es sind noch kaum Fehlerbehandlungsroutinen eingebaut! Bis jetzt ist es auch so, dass NodeCount unbedingt vor ElementList gesetzt werden muss (ein Henne-Ei-Problem für das ich bis jetzt keine überzeugende Lösung gefunden habe).
Einbauen will ich noch eine Speichern/Laden Funktion, die Möglichkeit, den BruteForce-Vorgang in beliebig viele Pakete aufzuteilen (Multithreading, Parallel Computing), sowie eine Ausgabe der Kombinationen wahlweise als array of string (bzw. TBFElementList). Ich habe auch schon mit dem Gedanken gespielt, beliebige Dinge kombinierbar zu machen (beispielsweise Integer, Objekte, etc). Aber ich bin mir nicht sicher, ob sich der Aufwand lohnen würde.

Ich würde mich freuen, wenn von euch noch Vorschläge und Anregungen kämen, wie man die Komponente noch erweitern könnte


Download der Klasse im ersten Post im Anhang
Eine Demo mit der neuen Klasse gibt es in kürze.

[Diamondback2007]

ja das klappt ja alles schon ganz gut
allerdings wie du schon geasgt hast sind vor allem die teilbarkeit der aufgaben und das laden und speichern sehr wichtig.
das hat das ganze auch für mich attraktiv gemacht
die verwendung ist sehr gut und einfach gelungen.
wie kann man denn die konstaten für das alphabet kombinieren? kann man die arrays irgendwie addieren?

also wenn du das kombinieren noch etwas optimierst und den oben genannten kram einbaust hat sich das neuschreiben auf jeden fall gelohnt.

gruß

[Meflin]

Zitat von Diamondback2007:

allerdings wie du schon geasgt hast sind vor allem die teilbarkeit der aufgaben und das laden und speichern sehr wichtig.

Das sollte auf jeden Fall machbar sein. Nur fürchte ich wird das nochmal ein größerer Act

Zitat:

die verwendung ist sehr gut und einfach gelungen.

Das freut mich - so soll es sein

Zitat:

wie kann man denn die konstaten für das alphabet kombinieren? kann man die arrays irgendwie addieren?

Nicht ala ArrayA + ArrayB. Bis jetzt ist da eine self-made-Funktion nötig, aber ich kann natürlich eine in die Unit integrieren.

Zitat:

also wenn du das kombinieren noch etwas optimierst

Leichter gesagt als getan

[QuickAndDirty]

Das beste in dem Thread ist noch das Kommentar von Insider2004...lol
Nicht das BruteForce ein allgemein übliches verfahren für zig
Standard Probleme der Informatik wäre(Handlungsreisender, Volumen mit unterschiedlichen Packeten Optimal befüllen, etc.)
Und dann Heist der auch noch "Insider"....Ich schmeiß mich weg.

[Diamondback2007]

Zitat von Meflin:

Zitat von Diamondback2007:

allerdings wie du schon geasgt hast sind vor allem die teilbarkeit der aufgaben und das laden und speichern sehr wichtig.

Das sollte auf jeden Fall machbar sein. Nur fürchte ich wird das nochmal ein größerer Act

na dann hau mal rein ich denke, das wichtigste ist das prinzip wie du speicherst. ich weiß jetzt nicht so genau wie du deine strings zusammensetzt, aber wenn du das einigermaßen geschickt machst, sollte es eigentlich möglich sein das hinzubekommen.
wenn du allerdings bei einem bestimmten string anfangen kannst zu rechen, ist das aufteilen auf mehrere pcs natürlich schon praktisch fertig.

Zitat von Meflin:

Zitat von Diamondback2007:

wie kann man denn die konstaten für das alphabet kombinieren? kann man die arrays irgendwie addieren?

Nicht ala ArrayA + ArrayB. Bis jetzt ist da eine self-made-Funktion nötig, aber ich kann natürlich eine in die Unit integrieren.

ja, ich denke das wäre recht praktisch für die unit.

Zitat von Meflin:

Zitat von Diamondback2007:

also wenn du das kombinieren noch etwas optimierst

Leichter gesagt als getan

im DF habe ich grade gestern etwas darüber gelesen... und zwar das wenn du in etwa str := str + str2; hast, dass das sehr langsam ist weil erst wieder str eingelesen wird und dann str komplett neu geschrieben wird. Da wurde irgendwas von appendstr() geredet... keine ahnung, kannst du dich ja mal schlau machen.
ich hab außerdem gesehen, dass du das alles immer dem Result hinzufügst. ist das genauso schnell wie bei einer lokalen variable? oder kann man das noch optimieren indem man eine lokale variable nimmt und result erst zum schluss zuweist?

gruß

EDIT:

Also wenn ich AppendStr() benutze bringt das bei mir etwa 100.000 bis 300.000 Kombinationen pro sekunde mehr.

[Meflin]

Zitat von Diamondback2007:

wenn du allerdings bei einem bestimmten string anfangen kannst zu rechen, ist das aufteilen auf mehrere pcs natürlich schon praktisch fertig.

Kann ich. Das Problem ist eher, dass Rechner A dann auch bei dem string aufhört, bei dem Rechner B weitermacht

Zitat:

im DF habe ich grade gestern etwas darüber gelesen... und zwar das wenn du in etwa str := str + str2; hast, dass das sehr langsam ist weil erst wieder str eingelesen wird und dann str komplett neu geschrieben wird.

Nunja, in zahlreichen Tests hat sich herausgestellt, dass das so ziemlich die schnellste Variante ist
siehe hier und hier

Zitat:

Also wenn ich AppendStr() benutze bringt das bei mir etwa 100.000 bis 300.000 Kombinationen pro sekunde mehr.

Na das ist ja mal interessant. Denn bei mir ist AppendStr in etwa so implementiert (aus dem Gedächtnis):

Delphi-Quellcode:

function AppendStr(const Source: string; Dest: string): string;
begin
  Result := Dest + Source;
end;