Array-Work

[TS]

Hallo und gute Nacht,

ich brauch mal einen Denkanstoß, wie ich es am sparsamsten aufbauen kann...

Aufs Wesentliche reduziert:

Gegeben sind ein Array (A) mit IPs (V4) und CIDR-Suffixen und ein Array (B) nur mit IPs (V4).

Es soll nun festgestellt werden, ob die IP aus (B) schon in (A) eingetragen ist. Dabei kann es aber vorkommen, dass sie nicht diskret erwähnt wird (also mit Suffix 32), sondern nur zu einem Subnetz gehört. Das soll dann selbstverständlich auch als Treffer gelten.

Wie baue ich den Vergleich am besten auf, damit ich möglichst keine verschachtelten foreach()-Schleifen brauche?

Grüße
TS

[Christian Kruse]

Hallo TS,

Wie baue ich den Vergleich am besten auf, damit ich möglichst keine verschachtelten foreach()-Schleifen brauche?

Abhängig von der Menge der Daten ist das aber die beste Lösung.

Wenn es wirklich mehr als ein paar hundert Einträge sind, sorge dafür, dass der zu durchsuchende Array sortiert ist und verwende binary search. Der Algorithmus ist z.B. in der Wikipedia recht gut dokumentiert.

LG,
CK

[TS]

Hallo Christian, hallo liebe Helfer und Leser,

Wie baue ich den Vergleich am besten auf, damit ich möglichst keine verschachtelten foreach()-Schleifen brauche?

Abhängig von der Menge der Daten ist das aber die beste Lösung.

Wenn es wirklich mehr als ein paar hundert Einträge sind, sorge dafür, dass der zu durchsuchende Array sortiert ist und verwende binary search. Der Algorithmus ist z.B. in der Wikipedia recht gut dokumentiert.

Dazu möchte ich jetzt noch eine Rückmeldung geben. Da die Aufgabe nun soweit gelöst ist, dass nur noch das Skript aus Schnipseln in eine saubere Form gegossen werden muss...

Die Lösung mit den geschachtelten Arrays ist wirklich nicht langsam. Im Extremfall sind es bisher z. B. 320 x 580 = 185.600 Vergleiche (offensichtliche Optimierungsmöglichkeiten noch nicht durchgeführt). Inklusive Datenbeschaffung, Formatauswertung (Parsen der drei betroffenen Dateien), der ganzen Maskenrechnerei usw. braucht der Prozess trotzdem keine Sekunde. Ich hab's noch nicht genau gemessen, aber über Konsole kaum den Befehl abgeschickt, schon ist die Antwort da.

Kann jetzt auch daran liegen, dass auf dem Host noch nicht viel los ist (außer den Intruder-Knaben), aber für einen Job, der alle halbe Stunde einmal läuft, spendiere ich gerne eine Sekunde.

Grüße
TS

[mermshaus]

Spontane Idee: So ein Array…

$a = array(
    '192.168.11.12/24',
    '62.10.11.12/32',
    '128.10.11.12/8',
    '96.50.51.52/16'
);

…in diese Form überführen…

$a2 = array(
    '192.168.11' => true,
    '62.10.11.12' => true,
    '128' => true,
    '96.50' => true
};

…und dann für jeden Eintrag aus $b in der Form w.x.y.z prüfen, ob w, w.x, w.x.y oder w.x.y.z als Index in $a2 existieren (isset).

Mal zusammengehackt:

<?php

$a = array(
    '192.168.11.12/24',
    '62.10.11.12/32',
    '128.10.11.12/8',
    '96.50.51.52/16'
);

$b = array(
    '192.168.128.0',   // kein Treffer
    '192.168.11.255',  // Treffer
    '62.10.11.255',    // kein Treffer
    '62.10.11.12',     // Treffer
    '128.255.255.255', // Treffer
    '129.255.255.255', // kein Treffer
    '96.50.255.255',   // Treffer
    '97.50.51.52'      // kein Treffer
);

function f(array $a)
{
    $new = array();

    foreach ($a as $item) {
        list($ipv4, $cidr) = explode('/', $item);
        $index = implode('.', array_slice(explode('.', $ipv4), 0, $cidr >> 3));
        $new[$index] = true;
    }

    return $new;
}

function g(array $a2, array $b)
{
    foreach ($b as $item) {
        $parts = explode('.', $item);
        $tmp = '';

        for ($i = 0; $i <= 3; $i++) {
            $tmp .= (('' !== $tmp) ? '.' : '') . $parts[$i];

            if (isset($a2[$tmp])) {
                echo $item . '- Treffer' . "\n";
                continue 2;
            }
        }

        echo $item . ' - kein Treffer' . "\n";
    }
}

$a2 = f($a);
g($a2, $b);

→ Demo

[dedlfix]

Tach!

[Netzmasken streichen] …und dann für jeden Eintrag aus $b in der Form w.x.y.z prüfen, ob w, w.x, w.x.y oder w.x.y.z als Index in $a2 existieren (isset).

Der Ansatz liefert falsche Ergebnisse, wenn die Netzmasken andere sind als 8, 16 und 24.

Das bekommt man besser hin, wenn man Bitoperationen auf den numerischen Wert der Adressen (ip2long()) verwendet: A-Adresse mit Broadcast-Adresse von dessen Netzwerk Oder-Verknüpfen und zum Test die B-Adresse Und-Verknüpfen. 0 == enthalten.

Außerdem ging es doch hauptsächlich darum, verschachtelte foreach zu vermeiden.

dedlfix.

[mermshaus]

Der Ansatz liefert falsche Ergebnisse, wenn die Netzmasken andere sind als 8, 16 und 24.

Sorry, hatte nicht darüber nachgedacht, ob es die gibt. Dann muss man es anders angehen, ja.

Außerdem ging es doch hauptsächlich darum, verschachtelte foreach zu vermeiden.

Und da gilt ein Umstellen des Arrays $a nicht?

[dedlfix]

Tach!

Außerdem ging es doch hauptsächlich darum, verschachtelte foreach zu vermeiden.

Und da gilt ein Umstellen des Arrays $a nicht?

Dieser Satz sollte sich nicht auf das Umstellen beziehen, sondern auf die Lösung insgesamt.

dedlfix.

[mermshaus]

Außerdem ging es doch hauptsächlich darum, verschachtelte foreach zu vermeiden.

Und da gilt ein Umstellen des Arrays $a nicht?

Dieser Satz sollte sich nicht auf das Umstellen beziehen, sondern auf die Lösung insgesamt.

Sorry, ich verstehe nicht, was du meinst. Ich habe eine mehr oder weniger lineare Laufzeit. Ich löse nur nicht das komplette Problem. Die for-Schleife in g() dient dazu, Schreibarbeit zu sparen. :) Sie ist aber von der Größe der Eingaben unabhängig.

[dedlfix]

Tach!

Sorry, ich verstehe nicht, was du meinst. Ich habe eine mehr oder weniger lineare Laufzeit.

Mein Fehler, ich hab nicht genau hingeschaut. Aber mal angenommen, deine Lösung wäre funktionabel (das for fiele dabei sicher weg), dann wäre da zwar nur ein linearer Durchlauf zu sehen (ohne Array-Umformen), aber müsstest du dann nicht auch noch den internen Hash-Zugriff in die Bewertung einbeziehen, und bekäme dann nicht das Wort "weniger" eine größere Gewichtung?

dedlfix.

[mermshaus]

Mein Fehler, ich hab nicht genau hingeschaut. Aber mal angenommen, deine Lösung wäre funktionabel (das for fiele dabei sicher weg), dann wäre da zwar nur ein linearer Durchlauf zu sehen (ohne Array-Umformen), aber müsstest du dann nicht auch noch den internen Hash-Zugriff in die Bewertung einbeziehen, und bekäme dann nicht das Wort "weniger" eine größere Gewichtung?

Das kann ich aus dem Stegreif leider auch nicht beantworten. Ich rechne immer erst mal naiv mit O(1) für einen Lookup in so einer PHP Hash-Map. Das ist nicht der worst case. Bislang habe ich durch Hash-Maps immer den Performance-Zuwachs erreicht, den ich erwartet habe beziehungsweise der mir ausgereicht hat. (Performance-Fragen… Schwieriges Thema.) Ich hatte deshalb noch keine Notwendigkeit, mich mit den Nuancen zu befassen. Im Grunde ist das auch müßig, weil die ab einem gewissen Punkt ohnehin Implementationsdetail der Engine sind. Auf PHP-Ebene hat man es letztlich gar nicht so sehr in der Hand.

Hier mal meine vorläufige überarbeitete Version von f() und g() (der Einfachheit halber poste ich wieder alles):

(Rechnet mit Fehlern. ;) Ich habe gerade nicht die Muße, ordentliche Tests zu schreiben. Das ist knifflig für Netzmasken, deren Bitzahl nicht durch 8 teilbar ist. Der Code ist auch noch nicht wirklich durchdacht.)

<?php

$a = array(
    '192.168.11.12/24',
    '62.10.11.12/32',
    '128.10.11.12/8',
    '96.50.51.52/16',

    '192.168.1.188/27'
);

$b = array(
    '192.168.128.0',   // kein Treffer
    '192.168.11.255',  // Treffer
    '62.10.11.255',    // kein Treffer
    '62.10.11.12',     // Treffer
    '128.255.255.255', // Treffer
    '129.255.255.255', // kein Treffer
    '96.50.255.255',   // Treffer
    '97.50.51.52',     // kein Treffer

    '192.168.1.189',   // Treffer
    '192.168.1.89'     // kein Treffer
);

function f(array $a)
{
    $new = array();

    foreach ($a as $item) {
        list($ipv4, $cidr) = explode('/', $item);

        $iplong = ip2long($ipv4);

        $iplong >>= 32 - $cidr;

        if (!isset($new[$cidr])) {
            $new[$cidr] = array();
        }

        $new[$cidr][$iplong] = true;
    }

    return $new;
}

function g(array $a2, array $b)
{
    foreach ($b as $item) {

        $iplong = ip2long($item);

        for ($i = 1; $i <= 32; $i++) {
            if (isset($a2[$i][$iplong >> 32 - $i])) {
                echo $item . '- Treffer' . '(' . $i .  ')' . "\n";
                continue 2;
            }
        }

        echo $item . ' - kein Treffer' . "\n";
    }
}

$a2 = f($a);

g($a2, $b);

→ Demo

Ansonsten würde ich aber auch den Usecase abwarten wollen, was weitere Optimierungen angeht (die mit Sicherheit möglich sind).

Edit: Unwesentliche Anpassung.

[Rolf b]

Du brauchst in $new kein 2D-Array, die Subnetze bilden per Definition einen präfixfreien Code. Die errechneten $iplong-Werte in f dürften bei realitätsnahen Inhalten im $a Array keine Doubletten bilden. Es sei denn, du hantierst mit historischen Daten und hast Subnetzangaben, die später aufgeteilt wurden.

Du solltest auch den ip2long Wert nach rechts shiften, sondern aus der Präfixlänge die Subnetzmaske bestimmen (über eine Lookup-Tabelle) und dann $iplong & $subnetmask als Key für $a2 verwenden. Dann kannst Du in g nämlich über alle 31 möglichen Subnetzmasken gehen und mit array_key_exists in $a2 prüfen, ob $b & $subnetmask enthalten ist. Bei vielen Einträgen in $a ist das effizienter.

Eine weitere Optimierung wäre, in $a die tatsächlich genutzten Subnetzmasken als Keys eines Arrays zu sammeln und in g nur diese für die Suche zu nutzen.

Rolf

[mermshaus]

Danke für die Antwort.

Du brauchst in $new kein 2D-Array, die Subnetze bilden per Definition einen präfixfreien Code. Die errechneten $iplong-Werte in f dürften bei realitätsnahen Inhalten im $a Array keine Doubletten bilden. Es sei denn, du hantierst mit historischen Daten und hast Subnetzangaben, die später aufgeteilt wurden.

Das verstehe ich leider nicht. Ich speichere die Bitlänge mit, weil ich meines Erachtens sonst nicht wissen kann, auf wie viele Stellen ich eine zu prüfende IP aus $b testen muss. Also, um etwa zwischen 192.168.0.0/16 und 192.168.0.0/24 unterscheiden zu können. Das war zumindest mein Gedanke dazu.

Du solltest auch den ip2long Wert [nicht] nach rechts shiften, sondern aus der Präfixlänge die Subnetzmaske bestimmen (über eine Lookup-Tabelle) und dann $iplong & $subnetmask als Key für $a2 verwenden. Dann kannst Du in g nämlich über alle 31 möglichen Subnetzmasken gehen und mit array_key_exists in $a2 prüfen, ob $b & $subnetmask enthalten ist. Bei vielen Einträgen in $a ist das effizienter.

Das könnte sinnvoll sein. Werde ich umstellen.

Eine weitere Optimierung wäre, in $a die tatsächlich genutzten Subnetzmasken als Keys eines Arrays zu sammeln und in g nur diese für die Suche zu nutzen.

Ja, das habe ich in meiner lokalen Version bereits drin.

Man könnte bei der Umwandlung von $a nach $a2 noch Teilmengen rausnehmen.

$a = array(
    '62.120.0.0/8',
    '62.120.0.0/16' // <-- wird bereits durch Zeile darüber abgedeckt
);

[Rolf b]

Man könnte bei der Umwandlung von $a nach $a2 noch Teilmengen rausnehmen.

$a = array(
    '62.120.0.0/8',
    '62.120.0.0/16' // <-- wird bereits durch Zeile darüber abgedeckt
);

Genau das meinte ich mit präfixfreiem Code. Dieses Array kann bei korrekter Subnetzdefinition nicht entstehen, weil Du die IPv4 Welt nicht auf diese Weise aufteilen kannst. In welches Subnetz müsstest Du die Adresse 62.120.47.11 denn nun routen?

Ausflug in die theoretische Informatik: Ein Code ist präfixfrei, wenn niemals ein Codewort Präfix eines anderen ist. Wenn ein Code die Wörter "AB" und "ABE" enthält, ist er nicht präfixfrei. Dein Array ist auch nicht präfixfrei, weil 62.120.0.0/8 als Präfix von 62.120.0.0/16 aufgefasst werden kann.

Wenn Du ein präfixfreies $a Array hast, kannst Du jeden Eintrag durch seine Basisadresse repräsentieren. Wenn du eine IP in $b dann der Reihe nach mit Subnetzmasken für die Präfixlängen von 1-32 maskierst und das Ergebnis in der Hashmap suchst, findest Du sie eindeutig. Die Optimierung ist, eine Liste der tatsächlich in $a verwendeten Präfixlängen zu speichern und nur diese Längen auszuprobieren. Eine Optimierung 2 wäre, für jede verwendete Länge eine eigene Hashtable zu erzeugen und diese Tables der Reihe nach durchzugehen. Okay, das ist dein 2D Array. Da die Suche in einer Hashtable (sprich: Array-Keys) aber in O(1) erfolgt, bringt das kaum etwas.

Rolf

[mermshaus]

Man könnte bei der Umwandlung von $a nach $a2 noch Teilmengen rausnehmen.

$a = array(
    '62.120.0.0/8',
    '62.120.0.0/16' // <-- wird bereits durch Zeile darüber abgedeckt
);

Genau das meinte ich mit präfixfreiem Code. Dieses Array kann bei korrekter Subnetzdefinition nicht entstehen, weil Du die IPv4 Welt nicht auf diese Weise aufteilen kannst. In welches Subnetz müsstest Du die Adresse 62.120.47.11 denn nun routen?

Das ist im Rahmen der Problemstellung, eine effiziente Lookup-Funktion zu schreiben, nicht so sehr von Bedeutung. Es lässt sich nun mal ohne weiteren Vorbau nicht verhindern, dass Anwender derlei Angaben für $a übergeben. Die mögen inhaltlich zwar vielleicht wenig Sinn ergeben, aber sie sind im Sinne einfacher formaler Checks erst mal korrekt.

Wenn Du ein präfixfreies $a Array hast, kannst Du jeden Eintrag durch seine Basisadresse repräsentieren. Wenn du eine IP in $b dann der Reihe nach mit Subnetzmasken für die Präfixlängen von 1-32 maskierst und das Ergebnis in der Hashmap suchst, findest Du sie eindeutig.

Da kann ich noch immer nicht folgen. Wahrscheinlich verstehe ich es falsch. Ich schildere mal meinen Denkweg: Ich könnte in $a eine Eingabe 192.168.0.0/24 haben. Die Subnetzmaske dazu wäre 255.255.255.0. Wenn ich das mit 192.168.0.0 UND-verknüpfe, bleibe ich bei 192.168.0.0 als Eintrag in $a2. Das wäre aber der gleiche Wert wie für 192.168.0.0/16. Wenn ich in $b dann eine IP 192.168.255.20 habe, würde mir die für 192.168.0.0/24 fälschlicherweise als Treffer in $a2 ausgewertet, obwohl sie nur für 192.168.0.0/16 ein Treffer wäre.

[TS]

Hallo und guten Morgen,

Da kann ich noch immer nicht folgen. Wahrscheinlich verstehe ich es falsch. Ich schildere mal meinen Denkweg: Ich könnte in $a eine Eingabe 192.168.0.0/24 haben. Die Subnetzmaske dazu wäre 255.255.255.0. Wenn ich das mit 192.168.0.0 UND-verknüpfe, bleibe ich bei 192.168.0.0 als Eintrag in $a2. Das wäre aber der gleiche Wert wie für 192.168.0.0/16. Wenn ich in $b dann eine IP 192.168.255.20 habe, würde mir die für 192.168.0.0/24 fälschlicherweise als Treffer in $a2 ausgewertet, obwohl sie nur für 192.168.0.0/16 ein Treffer wäre.

Das 192.168.0.0/16 ist ein mögliches Supernet für 192.168.0.0/24.

Wenn Du das gesamte Supernet sperrst, sind auch alle darin befindlichen Subnets gesperrt. Folglich wäre es richtig, dass auch 192.168.0.0/32 (also die Client-IP) gesperrt würde.

@Christian Kruse: Können wir einen Tag "Routing" haben?

Grüße
TS

[Christian Kruse]

Hallo TS,

@Christian Kruse: Können wir einen Tag "Routing" haben?

Warum fragst du das mich? ;-) Ich bin nur der Techniker.

LG,
CK

[Auge]

Hallo

@Christian Kruse: Können wir einen Tag "Routing" haben?

Mach's doch selbst. Laut deinem Profil darfst du das seit dem 12.10. dieses Jahres um 7:12 Uhr (*brrr*, mitten in der Nacht).

Tschö, Auge

[TS]

Hallo und guten Morgen,

Mach's doch selbst. Laut deinem Profil darfst du das seit dem 12.10. dieses Jahres um 7:12 Uhr (*brrr*, mitten in der Nacht).

Ich hab's zwar geahnt, aber noch nicht gesehen wo und wie das geht... Muss ich also nochmal genauer hinsehen. Danke für den Hinweis :-)

Grüße
TS

[Christian Kruse]

Hallo TS,

Mach's doch selbst. Laut deinem Profil darfst du das seit dem 12.10. dieses Jahres um 7:12 Uhr (*brrr*, mitten in der Nacht).

Ich hab's zwar geahnt, aber noch nicht gesehen wo und wie das geht... Muss ich also nochmal genauer hinsehen. Danke für den Hinweis :-)

Einfach nur als Tag in der Textbox unten eingeben. Du bekommst dann eine Warning, dass der Tag nicht existiert und angelegt werden würde.

LG,
CK

[TS]

Hallo und guten Morgen,

Ich hab's zwar geahnt, aber noch nicht gesehen wo und wie das geht... Muss ich also nochmal genauer hinsehen. Danke für den Hinweis :-)

Einfach nur als Tag in der Textbox unten eingeben. Du bekommst dann eine Warning, dass der Tag nicht existiert und angelegt werden würde.

Ok.

Beim nächsten Mal.

Grüße
TS

[Auge]

Hallo

Beim nächsten Mal.

Wieso „Beim nächsten Mal“? Du darfst einem Beitrag im nachhinein Tags hinzufügen, ändern oder löschen. Und das seit über einem Jahr. In Kombination mit deinem Recht, neue Tags zu erstellen, kannst du den neuen Tag auch erstellen, indem du ihn einem bereits vorhandenen Beitrag hinzufügst.

Nutze die Macht, Tom!

Tschö, Auge

[TS]

Hallo und guten Tag,

[...] Du darfst [...]

Nutze die Macht, Tom!

Na gut ;-)

Was willst Du trinken?

Grüße
TS

[Auge]

Hallo

Mach's doch selbst. Laut deinem Profil darfst du das seit dem 12.10. dieses Jahres um 7:12 Uhr (*brrr*, mitten in der Nacht).

Ich hab's zwar geahnt, aber noch nicht gesehen wo und wie das geht...

Du gibst einfach das nicht existente Tag in das Eingabefeld ein. Es kommt eine Mitteilung, dass das Tag nicht existiert und angelegt wird, wenn du das Posting absendest ^[1]. Und dann machst du das Letztere einfach und gut is'.

Tschö, Auge

---

1. Warum die Mitteilung als Warnung formatiert ist, steht auf einem anderen Blatt. ↩︎

[Christian Kruse]

Hallo Auge,

Warum die Mitteilung als Warnung formatiert ist, steht auf einem anderen Blatt.

Weil es mehrfach aus Versehen passiert ist.

LG,
CK

[Rolf b]

Ich hoffe, du findest die Antwort noch nach dem ganzen Gequassel über Tags ;-)

Da kann ich noch immer nicht folgen. Wahrscheinlich verstehe ich es falsch. Ich schildere mal meinen Denkweg: Ich könnte in $a eine Eingabe 192.168.0.0/24 haben. Die Subnetzmaske dazu wäre 255.255.255.0. Wenn ich das mit 192.168.0.0 UND-verknüpfe, bleibe ich bei 192.168.0.0 als Eintrag in $a2. Das wäre aber der gleiche Wert wie für 192.168.0.0/16. Wenn ich in $b dann eine IP 192.168.255.20 habe, würde mir die für 192.168.0.0/24 fälschlicherweise als Treffer in $a2 ausgewertet, obwohl sie nur für 192.168.0.0/16 ein Treffer wäre.

Da Du die Aufgabe so definiert hast, dass ein Eintrag von $a2 Teilmenge eines anderen Eintrags sein kann, ist mein Hinweis auf Präfixfreiheit obsolet.

Andererseits - wenn dein $a Array 192.168.0.0/24 UND 192.168.0.0/16 enthält - und es Dir nur auf Treffer ankommt, nicht aber darauf, welcher Eintrag aus $a getroffen wurde, dann kannst Du im Vorverarbeitungsschritt den Eintrag 192.168.0.0/24 auch löschen. Der ist dann redundant. Falls es Dir aber AUCH darauf ankommt, ob Du den /24 oder den /16 Eintrag getroffen hast, dann musst Du sicherstellen, dass Du die längeren Präfixe zuerst testet. Tust Du das?

Rolf

[TS]

Hallo und gute Nacht,

Ich hoffe, du findest die Antwort noch nach dem ganzen Gequassel über Tags ;-)

Ja, ist manchmel zuviel Meta ;-)
@Christian Kruse: Kann man doch aber irgendwie ausblenden, oder?

Da kann ich noch immer nicht folgen. Wahrscheinlich verstehe ich es falsch. Ich schildere mal meinen Denkweg: Ich könnte in $a eine Eingabe 192.168.0.0/24 haben. Die Subnetzmaske dazu wäre 255.255.255.0. Wenn ich das mit 192.168.0.0 UND-verknüpfe, bleibe ich bei 192.168.0.0 als Eintrag in $a2. Das wäre aber der gleiche Wert wie für 192.168.0.0/16. Wenn ich in $b dann eine IP 192.168.255.20 habe, würde mir die für 192.168.0.0/24 fälschlicherweise als Treffer in $a2 ausgewertet, obwohl sie nur für 192.168.0.0/16 ein Treffer wäre.

Da Du die Aufgabe so definiert hast, dass ein Eintrag von $a2 Teilmenge eines anderen Eintrags sein kann, ist mein Hinweis auf Präfixfreiheit obsolet.

Andererseits - wenn dein $a Array 192.168.0.0/24 UND 192.168.0.0/16 enthält - und es Dir nur auf Treffer ankommt, nicht aber darauf, welcher Eintrag aus $a getroffen wurde, dann kannst Du im Vorverarbeitungsschritt den Eintrag 192.168.0.0/24 auch löschen. Der ist dann redundant. Falls es Dir aber AUCH darauf ankommt, ob Du den /24 oder den /16 Eintrag getroffen hast, dann musst Du sicherstellen, dass Du die längeren Präfixe zuerst testet. Tust Du das?

Vergisss nicht: die Regeln der einen Liste(A) sind nicht unbedingt identisch mit den Regeln der zweiten Liste(B).

Und es ist nicht sinnvoll, mitten im Thread die Bezeichner des OP gegen irgendwelche eigene zu wechseln... Es sei denn, dass das GAAAANZZZZ wichtig und unabwendbar war!

Und niemand sprach davon, dass die eine oder die andere Liste konsistent wären. Bezüglich der Sicherheit ist es sogar ein guter Ansatz, auch die möglichen Inkonsistenzen in beiden Listen und deren Relationen nebst Folgen zu betrachten! Also bitte nicht aufhören.

Grüße
TS

[Christian Kruse]

Hallo TS,

Ich hoffe, du findest die Antwort noch nach dem ganzen Gequassel über Tags ;-) Ja, ist manchmel zuviel Meta ;-)
@Christian Kruse: Kann man doch aber irgendwie ausblenden, oder?

Was? Tags? Falls ja: nein, die kann man von Haus aus nicht ausblenden.

LG,
CK

[mermshaus]

Habe es gefunden, danke. :) Ich poste mal nur noch mal meine letzte Version, da ich nicht glaube, dass ich ohne gegebenen Anlass noch was dran machen werde (sorry). Ich glaube, ich verstehe die eigentliche Problemstellung auch nicht so richtig, weil es nicht so sehr mein Bereich ist.

Vielleicht hilft es aber trotzdem irgendwem:

<?php

/**
 *
 */
class Algo
{
    /**
     * @var array
     */
    private $masks;

    /**
     * @var array
     */
    private $maskKeys;

    /**
     * @param array $masks
     */
    public function __construct(array $masks)
    {
        $this->masks = $this->rearrangeMasks($masks);
        $this->maskKeys = array_keys($this->masks);
        ksort($this->maskKeys);
    }

    /**
     * @param array $a
     * @return array
     */
    private function rearrangeMasks(array $a)
    {
        $new = array();

        foreach ($a as $item) {
            list($ipv4, $cidr) = explode('/', $item);

            $iplong = ip2long($ipv4);

            $iplong >>= 32 - $cidr;

            if (!isset($new[$cidr])) {
                $new[$cidr] = array();
            }

            $new[$cidr][$iplong] = true;
        }

        return $new;
    }

    /**
     * @param string $ipv4
     * @return bool
     */
    public function isMatch($ipv4)
    {
        $iplong = ip2long($ipv4);

        foreach ($this->maskKeys as $i) {
            if (isset($this->masks[$i][$iplong >> 32 - $i])) {
                return true;
            }
        }

        return false;
    }
}

/**
 *
 */
class AlgoTest extends PHPUnit_Framework_TestCase
{
    /**
     * @param string $bin
     * @return string
     */
    private function ipFromBin($bin)
    {
        $parts = explode('.', $bin);
        return implode('.', array_map('bindec', $parts));
    }

    /**
     * @param string $bin
     * @return string
     */
    private function maskFromBin($bin)
    {
        list($tmp, $cidr) = explode('/', $bin);
        return $this->ipFromBin($tmp) . '/' . $cidr;
    }

    /**
     * @param array $masks
     * @param array $assertions
     */
    private function runAssertions(array $masks, array $assertions)
    {
        $algo = new Algo($masks);

        foreach ($assertions as $assertion) {
            list($ipv4, $expected) = $assertion;
            $this->assertSame($expected, $algo->isMatch($ipv4), implode(', ', $masks) . ' : ' . $ipv4);
        }
    }

    /**
     *
     */
    public function testMain()
    {
        $masks = array(
            '192.168.11.12/24',
            '62.10.11.12/32',
            '128.10.11.12/8',
            '96.50.51.52/16'
        );

        $assertions = array(
            array('192.168.128.0', false),
            array('192.168.11.255', true),
            array('62.10.11.255', false),
            array('62.10.11.12', true),
            array('128.255.255.255', true),
            array('129.255.255.255', false),
            array('96.50.255.255', true),
            array('97.50.51.52', false)
        );

        $this->runAssertions($masks, $assertions);

        $masks = array(
            // 192.168.1.188/27 xxxxxxxx xxxxxxxx xxxxxxxx xxx-----
            $this->maskFromBin('11000000.10101000.00000001.10111100/27')
        );

        $assertions = array(
            array($this->ipFromBin('11000000.10101000.00000001.10111111'), true),
            array($this->ipFromBin('11000000.10101000.00000001.10100000'), true),

            array($this->ipFromBin('11000000.10101000.00000001.10011111'), false),
            array($this->ipFromBin('11000000.10101000.00000001.10000000'), false)
        );

        $this->runAssertions($masks, $assertions);

        $masks = array(
            // 192.168.1.188/1  x------- -------- -------- --------
            $this->maskFromBin('11000000.10101000.00000001.10111100/1')
        );

        $assertions = array(
            array($this->ipFromBin('11111111.11111111.11111111.11111111'), true),

            array($this->ipFromBin('01000000.10101000.00000001.10011111'), false)
        );

        $this->runAssertions($masks, $assertions);

        $masks = array(
            //                  xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
            $this->maskFromBin('11111111.11111111.11111111.11111111/32'),

            //                  xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
            $this->maskFromBin('00000000.00000000.00000000.00000000/32')
        );

        $assertions = array(
            array($this->ipFromBin('11111111.11111111.11111111.11111111'), true),
            array($this->ipFromBin('00000000.00000000.00000000.00000000'), true),

            array($this->ipFromBin('11111111.11111111.11111111.11111110'), false),
            array($this->ipFromBin('00000000.00000000.00000000.00000001'), false)
        );

        $this->runAssertions($masks, $assertions);

        $masks = array(
            //                  xxxxxxxx xxxx---- -------- --------
            $this->maskFromBin('11111111.11110000.00000000.00000000/12')
        );

        $assertions = array(
            array($this->ipFromBin('11111111.11110000.11111111.11111111'), true),

            array($this->ipFromBin('11111111.00001111.11111111.11111111'), false)
        );

        $this->runAssertions($masks, $assertions);
    }
}

[TS]

Hallo und gute Nacht,

danke. Ich guck es mir an und bunkere es dann in der Ideenkiste.

Meine Version hat auch schon funktionirt. Werde ich morgen noch dazu posten.

Grüße
TS

[TS]

Hallo und guten Morgen,

zunächst erstmal vielen Dank für deine Betrachtung und Musterlösung.

Ich habe mal gerechnet und komme in der Praxis auf ca. 150.000 bis 300.000 Vergleiche. Es wird ja Quasi ein kartesischey System aufgebaut.

Probleme habe ich aber auf jeden Fall noch mit der numerischen Länge.

Ursprünglich wollte ich rechnen

if ($ip1 & pow(2, $cidr)) == ($ip2 & pow(2, $cidr)))
{
    ## Treffer
}

aber das klappt nicht wegen der integer-Länge in PHP. Kommen denn die Shiftfunktionen mit 32Bit positiv zurecht?

Ich kanns leider nicht ausprobieren. Hab nur das Tablet zur Hand.

Grüße
TS

[TS]

Hallo und guten Morgen,

Ursprünglich wollte ich rechnen

if ($ip1 & pow(2, $cidr)) == ($ip2 & pow(2, $cidr)))
{
    ## Treffer
}

was aber sowieso verkehrt herum ist :-(
Mit Abstand sieht man dann sogar Bitfehler ohoh

Grüße
TS

[Rolf b]

Das Zweierkomplementformat der Integers macht die Sache für Dich sogar einfacher. Sei "L" die Präfixlänge.

L     Subnetzmaske   Int-Wert     Rechnung
32    FFFFFFFF        -1          -pow(2,0)
31    FFFFFFFE        -2          -pow(2,1)
30    FFFFFFFC        -4          -pow(2,2)
29    FFFFFFF8        -8          -pow(2,3)
28    FFFFFFF0       -16          -pow(2,4)
...
2     C0000000       -1073741824  -pow(2,30)
1     80000000       -2147483648  -pow(2,31)

Zu beachten bei POW ist nur, dass das eine Float-Funktion ist und keine Integer-Funktion. Das hat aber den Vorteil, dass Du pow(2,31) berechnen kannst, ohne darüber nachdenken zu müssen ob dein PHP durch einen 32-bit oder 64-bit Compiler auf die Welt gekommen ist (weil $$+2^{31}$$ kein gültiger 32-bit integer ist, $$-(2^{31})$$ dagegen schon). Und weil die Bit-Operatoren von PHP ihre Operanden automatisch nach integer konvertieren, kannst Du damit einfach loslegen. Und selbst wenn PHP die pow-Funktion nach der Taschenrechner-Methode umsetzt ($$a^b = e^{b\cdot \ln a}$$), sollte es hinreichend genau sein, um nach INT-Konvertierung die Zweierpotenzen richtig zu treffen, weil die PHP floats laut Handbuch immer 64-bittig sind (also eigentlich double).

Also: Subnetzmaske = -pow(2, 32-l) und gut ist.

Ich kann hier nur nicht ausprobieren ob es eine versteckte Tücke dabei gibt, kein PHP zur Hand...

Rolf

[pl]

Hallo und gute Nacht,

ich brauch mal einen Denkanstoß, wie ich es am sparsamsten aufbauen kann...

Aufs Wesentliche reduziert:

Gegeben sind ein Array (A) mit IPs (V4) und CIDR-Suffixen und ein Array (B) nur mit IPs (V4).

Es soll nun festgestellt werden, ob die IP aus (B) schon in (A) eingetragen ist. Dabei kann es aber vorkommen, dass sie nicht diskret erwähnt wird (also mit Suffix 32), sondern nur zu einem Subnetz gehört. Das soll dann selbstverständlich auch als Treffer gelten.

Wie baue ich den Vergleich am besten auf, damit ich möglichst keine verschachtelten foreach()-Schleifen brauche?

In Perl würde ich über map{}

my %hunt = map{$_->[0] => 1}map{[split(/\//, $_)]} @A;

die CIDR-Schnippel abschneiden und einen Hash mit IP's erzeugen, so dass danach mit eimem einzigen Schleifendurchlauf über die B-Liste geprüft werden kann, ob eine B-IP in %hunt einen Treffer liefert.

MfG

[Christian Kruse]

Hallo pl,

In Perl würde ich über map{}

my %hunt = map{$_->[0] => 1}map{[split(/\//, $_)]} @A;

die CIDR-Schnippel abschneiden und einen Hash mit IP's erzeugen, so dass danach mit eimem einzigen Schleifendurchlauf über die B-Liste geprüft werden kann, ob eine B-IP in %hunt einen Treffer liefert.

Aufgabenstellung nochmal lesen. Die IPs können auch nur im gleichen Netz liegen, definiert durch die CIDR. Es muss kein genauer Treffer sein. Ein Hash-Lookup ist keine geeignete Lösung.

LG,
CK

[pl]

Hallo Christian,

das mag für PHP stimmen, meine Lösung war aber für Perl.

[Christian Kruse]

Hallo pl,

das mag für PHP stimmen, meine Lösung war aber für Perl.

???

Deine Lösung ist unabhängig von der Sprache falsch. Du machst einen Hash-Lookup und wirst für den Fall „IP-Adresse existiert nicht in der Suchmenge, ist aber Teil eines vermerkten Netzwerks“ keinen Treffer finden.

LG,
CK

[TS]

Hallo und guten Morgen,

die CIDR-Schnippel abschneiden und einen Hash mit IP's erzeugen, so dass danach mit eimem einzigen Schleifendurchlauf über die B-Liste geprüft werden kann, ob eine B-IP in %hunt einen Treffer liefert.

Aufgabenstellung nochmal lesen. Die IPs können auch nur im gleichen Netz liegen, definiert durch die CIDR. Es muss kein genauer Treffer sein. Ein Hash-Lookup ist keine geeignete Lösung.

Ja, so ist das leider gedacht. Und dabei ist eben das Hauptproblem, dass die CIDR bei der Netz-IP ("Heuhaufen") steht und nicht bei der zu prüfenden ("Nadel"). Man weiß also ohne die Netz-IP nicht, wieviele Bits relevant sind.

Aber die Diskussion hat für mich bereits ergeben, dass ich ja nach dem ersten Treffer aufhören kann zu suchen. Ich müsste also am besten über die CIDR sortieren, kleinste zuerst

So würde das ein Router wohl auch machen ;-)

Bleibt jetzt also "nur noch" mein Problem mit der numerischen Länge.

Grüße
TS
(vom Tablet)

[pl]

Hallo und guten Morgen,

die CIDR-Schnippel abschneiden und einen Hash mit IP's erzeugen, so dass danach mit eimem einzigen Schleifendurchlauf über die B-Liste geprüft werden kann, ob eine B-IP in %hunt einen Treffer liefert.

Aufgabenstellung nochmal lesen. Die IPs können auch nur im gleichen Netz liegen, definiert durch die CIDR. Es muss kein genauer Treffer sein. Ein Hash-Lookup ist keine geeignete Lösung.

Ja, so ist das leider gedacht. Und dabei ist eben das Hauptproblem, dass die CIDR bei der Netz-IP ("Heuhaufen") steht und nicht bei der zu prüfenden ("Nadel"). Man weiß also ohne die Netz-IP nicht, wieviele Bits relevant sind.

Dafür gibt es eine Default-Mask (siehe auch Default Class).

Aber die Diskussion hat für mich bereits ergeben, dass ich ja nach dem ersten Treffer aufhören kann zu suchen. Ich müsste also am besten über die CIDR sortieren, kleinste zuerst

So würde das ein Router wohl auch machen ;-)

Ein classful Router guckt sich die Maske gar nicht erst an, sondern nur die ersten Bit's. Die Maske kommt erst bei classless Routing ins Spiel /CIDR.

Bleibt jetzt also "nur noch" mein Problem mit der numerischen Länge.

Router bilden eine sog. Summary, wenns entsprechend konfiguriert ist, werden Netze zusammengefasst, auch als Super-Netting bezeichnet.

Überlege Dir, wass Du überhaupt berechnen willst dann ist das nur noch Tipparbeit.

Netze kalkulieren

[TS]

Hallo und guten Abend,

erstaunt guck

Ja, so ist das leider gedacht. Und dabei ist eben das Hauptproblem, dass die CIDR bei der Netz-IP ("Heuhaufen") steht und nicht bei der zu prüfenden ("Nadel"). Man weiß also ohne die Netz-IP nicht, wieviele Bits relevant sind.

Dafür gibt es eine Default-Mask (siehe auch Default Class).

hä? WIe meinst Du das? Meine Aufgabenstellung war doch deutlich beschrieben.

Aber die Diskussion hat für mich bereits ergeben, dass ich ja nach dem ersten Treffer aufhören kann zu suchen. Ich müsste also am besten über die CIDR sortieren, kleinste zuerst

So würde das ein Router wohl auch machen ;-)

Ein classful Router guckt sich die Maske gar nicht erst an, sondern nur die ersten Bit's. Die Maske kommt erst bei classless Routing ins Spiel /CIDR.

Ich sprach aber von "CIDR" und das ist doch wohl eindeutig classless Routing. Und das "So würde das ein Router wohl auch machen" bezieht sich auf das Sortieren der Liste nach (IP und) CIDR-Suffix. Beim Vergleichen kann er dann abbrechen, wenn das Netz mit dem kleineren Suffix passt.

Bleibt jetzt also "nur noch" mein Problem mit der numerischen Länge.

Router bilden eine sog. Summary, wenns entsprechend konfiguriert ist, werden Netze zusammengefasst, auch als Super-Netting bezeichnet.

Genau, das Netz mit dem kleinsten Suffix, das passt, ist das Supernet.

Überlege Dir, wass Du überhaupt berechnen willst dann ist das nur noch Tipparbeit.

Dachte ich auch, bis ich feststellen musste, dass bei PHP mal wieder der Teufel im Detail steckt. In Assembler wäre es ganz schnell gegangen, aber da fehtl mir dann der ganze Anzeigequark, der (nicht erwähnt, da weitere Aufgabe) im Browser stattfinden soll.

Sonst hätte ich mich bestimmt nicht für PHP entschieden für diese Aufgabenstellung.

Grüße
TS

[TS]

Hallo und guten Tag,

hab mich jetzt doch mal an den Schreibtisch gequält...

Wo steckt der Denkfehler in meinem Testscript?

<?php  ### op2long.php ### utf-8 ### äöüÄÖÜ
header('Content-Type: text/plain');

$_ip[] = '255.255.255.255';
$_ip[] = '127.0.0.1';

foreach ($_ip as $key => $dotted)
{
    $iplong = ip2long($dotted);
    $rshift = $iplong >> 8;
    $ipv4   = long2ip($rshift);
    if ($iplong === FALSE)
    {
        echo "false:\t";
    }
    else
    {
        echo "true: \t";
    }
    echo "$dotted \t $iplong \t $rshift \t $ipv4 \r\n";
}

?>

ergibt:

true: 	255.255.255.255 	 -1 	 -1 	 255.255.255.255 
true: 	127.0.0.1 	 2130706433 	 8323072 	 0.127.0.0 

Ich komme mit dem Wertebreich vom Integer nicht klar für IPv4, denn MAXINT ist eben nur 31stellig für den Zahlenwert...

Grüße
TS

[Matthias Apsel]

Hallo TS,

Ich komme mit dem Wertebreich vom Integer nicht klar für IPv4, denn MAXINT ist eben nur 31stellig für den Zahlenwert...

$parts = explode(".", $_SERVER['REMOTE_ADDR']);
$integer_ip =  16777216 * $parts[0] + 65536 * $parts[1] + 256 * $parts[2] + $parts[3];

macht maximal irgendwas mit 4 Mrd (2^15). Weit weniger als 31 Stellen.

Bis demnächst
Matthias

[Der Martin]

Hallo,

Ich komme mit dem Wertebreich vom Integer nicht klar für IPv4, denn MAXINT ist eben nur 31stellig für den Zahlenwert...

$parts = explode(".", $_SERVER['REMOTE_ADDR']);
$integer_ip =  16777216 * $parts[0] + 65536 * $parts[1] + 256 * $parts[2] + $parts[3];

macht maximal irgendwas mit 4 Mrd (2^15). Weit weniger als 31 Stellen.

nein, hier liegst du falsch. Der erste Koeffizient 16777216 ist ja schon 2^24, das Ergebnis kann bis zu 2^32-1 sein. Aber ich nehme an, TS meinte 31 binäre Stellen, weil Integer von -2^31 bis +2^31-1 geht.

Ciao,
 Martin

[Matthias Apsel]

Hallo Der Martin,

macht maximal irgendwas mit 4 Mrd (2^15). Weit weniger als 31 Stellen.

nein, hier liegst du falsch. Der erste Koeffizient 16777216 ist ja schon 2^24, das Ergebnis kann bis zu 2^32-1 sein.

Ja. Tippfehler, aber die 4 Mrd stimmen.

Bis demnächst
Matthias

[TS]

Hallo und guten Morgen,

Hallo,

Ich komme mit dem Wertebreich vom Integer nicht klar für IPv4, denn MAXINT ist eben nur 31stellig für den Zahlenwert...

$parts = explode(".", $_SERVER['REMOTE_ADDR']);
$integer_ip =  16777216 * $parts[0] + 65536 * $parts[1] + 256 * $parts[2] + $parts[3];

macht maximal irgendwas mit 4 Mrd (2^15). Weit weniger als 31 Stellen.

nein, hier liegst du falsch. Der erste Koeffizient 16777216 ist ja schon 2^24, das Ergebnis kann bis zu 2^32-1 sein. Aber ich nehme an, TS meinte 31 binäre Stellen, weil Integer von -2^31 bis +2^31-1 geht.

Jau! So war das gemeint. Ich benötige alle 32 Bit vorzeichenlos.

Und wenn Ihr mein Testprogramm noch mit weiteren IPs füttert, solltet Ihr sehen, dass ip2long() und long2ip() nicht funktionieren. So ist das zumindest bei mir. Ich habe hier immer noch ein 32-Bit-System drunter und z. Zt nur PHP Ver 5.4.31

Also entweder habe ich einen dicken Denkklops drin, oder aber die beiden IP-Funktionen sind buggy.

Grüße
TS

[Matthias Apsel]

Hallo TS,

Also entweder habe ich einen dicken Denkklops drin, oder aber die beiden IP-Funktionen sind buggy.

Das Manual schreibt: „Da der integer-Typ von PHP vorzeichenbehaftet ist und viele IP-Adressen auf 32-bit Architekturen in einen negativen Integerwert aufgelöst werden, sollten Sie dort die Formatierungsangabe "%u" für sprintf() und printf() verwenden, um eine Stringrepräsentation der vorzeichenlosen IP-Adresse zu erhalten.“

Bis demnächst
Matthias

[TS]

Hallo und guten Tag,

Also entweder habe ich einen dicken Denkklops drin, oder aber die beiden IP-Funktionen sind buggy.

Das Manual schreibt: „Da der integer-Typ von PHP vorzeichenbehaftet ist und viele IP-Adressen auf 32-bit Architekturen in einen negativen Integerwert aufgelöst werden, sollten Sie dort die Formatierungsangabe "%u" für sprintf() und printf() verwenden, um eine Stringrepräsentation der vorzeichenlosen IP-Adresse zu erhalten.“

Das habe ich gelesen, kann aber mMn für meinen Fall nichts damit anfangen. Ich will die IPs ja nicht auf dem Bildschirm darstellen, sondern damit "rechnen".

Grüße
TS

[Christian Kruse]

Hallo TS,

Jau! So war das gemeint. Ich benötige alle 32 Bit vorzeichenlos.

Warum? Ob das Vorzeichen gesetzt ist oder nicht ist doch auch nur ein Bit. Statt 3758096384 ist es dann halt -536870912, die Information bleibt erhalten.

LG,
CK

[TS]

Hallo und guten Tag,

Jau! So war das gemeint. Ich benötige alle 32 Bit vorzeichenlos.

Warum? Ob das Vorzeichen gesetzt ist oder nicht ist doch auch nur ein Bit. Statt 3758096384 ist es dann halt -536870912, die Information bleibt erhalten.

Habe ich auch gedacht, aber in meinem Testscript scheint php das anders zu sehen. Die Umwandlung lässt sich scheinbar nicht wieder umkehren ( long2ip() ). Oder aber ich habe da wirklich noch einen dicken Denkklops drin. Darum habe ich ja gefragt...

Grüße
TS

[Christian Kruse]

Hallo TS,

Jau! So war das gemeint. Ich benötige alle 32 Bit vorzeichenlos.

Warum? Ob das Vorzeichen gesetzt ist oder nicht ist doch auch nur ein Bit. Statt 3758096384 ist es dann halt -536870912, die Information bleibt erhalten.

Habe ich auch gedacht, aber in meinem Testscript scheint php das anders zu sehen. Die Umwandlung lässt sich scheinbar nicht wieder umkehren ( long2ip() ).

In deinem Test-Script machst du einen Shift um 8 Bit nach rechts. Warum du das machst bzw was du damit erreichen willst, kann ich nicht beurteilen, aber ich kann dir sagen, dass damit nicht unbedingt eine gültige IP bei rauskommt: im wesentlichen setzt du damit die erste Ziffer auf 0.

Was möchtest du mit dem Script denn erreichen?

LG,
CK

[TS]

Hallo und guten Morgen,

Jau! So war das gemeint. Ich benötige alle 32 Bit vorzeichenlos.

Warum? Ob das Vorzeichen gesetzt ist oder nicht ist doch auch nur ein Bit. Statt 3758096384 ist es dann halt -536870912, die Information bleibt erhalten.

Habe ich auch gedacht, aber in meinem Testscript scheint php das anders zu sehen. Die Umwandlung lässt sich scheinbar nicht wieder umkehren ( long2ip() ).

In deinem Test-Script machst du einen Shift um 8 Bit nach rechts. Warum du das machst bzw was du damit erreichen willst, kann ich nicht beurteilen, aber ich kann dir sagen, dass damit nicht unbedingt eine gültige IP bei rauskommt: im wesentlichen setzt du damit die erste Ziffer auf 0.

Genau! Ich setze damit das erste Oktett auf null, aber nur, wenn die Funktionen alle so funktionieren, wie sie beschrieben sind!

Versuch nochmal mit mehr IPs:

<?php  ### op2long.php ### utf-8 ### äöüÄÖÜ
header('Content-Type: text/plain');

$_ip[] = '255.255.255.255';
$_ip[] = '127.0.0.1';
$_ip[] = '224.13.14.15';
$_ip[] = '192.168.178.5';

foreach ($_ip as $key => $dotted)
{
    $iplong = ip2long($dotted);
    $rshift = $iplong >> 8;
    $ipv4   = long2ip($rshift);
    if ($iplong === FALSE)
    {
        echo "false:\t";
    }
    else
    {
        echo "true: \t";
    }
    echo "$dotted \t $iplong \t $rshift \t $ipv4 \r\n";
}

?>

ergibt:

true: 	255.255.255.255 	 -1 	 -1 	 255.255.255.255 
true: 	127.0.0.1 	 2130706433 	 8323072 	 0.127.0.0 
true: 	224.13.14.15 	 -536015345 	 -2093810 	 255.224.13.14 
true: 	192.168.178.5 	 -1062686203 	 -4151118 	 255.192.168.178 

Was möchtest du mit dem Script denn erreichen?

Das ordnungsmäße bzw. erwartungsgemäße Arbeiten der Funktionen überprüfen.

Später soll dann der Vergleich damit durchgeführt werden.

Grüße
TS

[TS]

Hallo und guten Tag Matthias,

Ich komme mit dem Wertebreich vom Integer nicht klar für IPv4, denn MAXINT ist eben nur 31stellig für den Zahlenwert...

$parts = explode(".", $_SERVER['REMOTE_ADDR']);
$integer_ip =  16777216 * $parts[0] + 65536 * $parts[1] + 256 * $parts[2] + $parts[3];

macht maximal irgendwas mit 4 Mrd (2^15). Weit weniger als 31 Stellen.

Da komme ich im Moment nicht mit, wie Du das meinst mit 16 Bit (= 2^15).

16777216 * $parts[0] => 16777216 * 255 => 1111 1111 0000 0000 0000 0000 0000 0000

Grüße
TS

[Matthias Apsel]

Hallo TS,

Da komme ich im Moment nicht mit, wie Du das meinst mit 16 Bit (= 2^15).

Tippfehler.

16777216 * $parts[0] => 16777216 * 255 => 1111 1111 0000 0000 0000 0000 0000 0000

Du willst eine Binärzahl als Dezimalzahl speichern?

Bis demnächst
Matthias

[TS]

Hallo und guten Morgen,

16777216 * $parts[0] => 16777216 * 255 => 1111 1111 0000 0000 0000 0000 0000 0000

Du willst eine Binärzahl als Dezimalzahl speichern?

Nein, ich will mit der binären Größe einer IP arbeiten. Obiges war nur an Matthias gerichtet, um ihm zu visualisieren, dass 16777216 * 255 volle 32 Bit benötigt.

Aber vielleicht muss ich mir die beiden Funktionen ip2long() und long2ip() emulieren und daraus ip2binarray() und binarray2ip() draus machen.

Das wird nur die Adressier- und Rechenarbeit für den Professor erheblich vergrößern und ein Übersystem aufbauen auf der Unzulänglichkeit einer Implementation vorhandener Fähigkeiten in der Basis in die Hochsprache. Ich kann mir einfach nicht vorstellen, dass die PHP-Leute da keinerlei Möglichkeit vorgesehen haben, binär unsigned auf ein Register zuzugreifen.

Kann mir bcmath eventuell dabei helfen? Irgendwie drehe ich mich im Kreis...

Grüße
TS

[Tagwächter]

Irgendwie drehe ich mich im Kreis...

Unterhalb von Abhilfe stehen zwei Links zu Skripten, die zwei Varianten von ip2dec liefern.

[Tagwächter]

Irgendwie drehe ich mich im Kreis...

Unterhalb von Abhilfe stehen zwei Links zu Skripten, die zwei Varianten von ip2dec liefern.

Beide funktioneren (siehe: FTX-Blocklist) auf einem 32-Bit System (armel).

[TS]

Hallo J.,

Unterhalb von Abhilfe stehen zwei Links zu Skripten, die zwei Varianten von ip2dec liefern.

Nein, aber so schnell bin ich nicht. Hier bimmelt dauernd das Telefon...

Grüße
TS

[Tagwächter]

long und die IP hat 4 Bytes: 2^32 = 4294967296

Mit Vorzeichen hat long aber aber nur: 2^31 = 2147483648 (Genauer: –2147483648 .. [phone]) - weshalb die Arbeit mit den Ergebnissen von iplong() nicht in allen Fällen wie vorgesehen funktioniert.

Abhilfe:

• Variante 1: ip2dec($ip)
• Variante 2: ip2dec($ip)

[Rolf b]

Klar kommst du klar. Du darfst den Wert auf einem 32-bit System nur nicht blindlings verwenden. Musst Du meistens aber auch gar nicht.

Die typischen Prozessoren haben zwei Rechts-Schiebebefehle: ASR und LSR. Und nein, den Befehl AFD haben sie zu dem Zweck nicht. ASR heißt "Arithmetic Shift Right" und füllt den beim Schieben freiwerdenden Raum mit dem Wert des obersten Bits derjenigen Zahl auf, die geschoben wird. Dadurch behält die Zahl ihr Vorzeichen bei. LSR (Logical Shift Right) füllt den freiwerdenden Raum mit Null auf.

Offenbar verwendet PHP den ASR Befehl, und deshalb würde bspw. 0x80 >> 3 zu 0xF0. Wenn man das als 8-bittige, vorzeichenbehaftete Integers ansähe, würde -128 zu -16, was korrekt einer Division durch $$2^3=8$$ entspricht.

Nun sind IPs aber vorzeichenlos - im Gegensatz zu den INT-Werten von PHP. Damit werden alle IPs, deren erste Zahl größer ist als 127, zu negativen INT32 Werten, und Bit-Shifts führen zu Merkwürdigkeiten.

Wenn Du auf Schieberei verzichtest und lediglich die Bit-Operatoren verwendest (& | und ~), ist alles gut. Wie Du mit 32-bit Integers aus der Präfixlänge eine Subnetzmaske machst, habe ich oben beschrieben (-pow(2, 32-$prefixlaenge)).

Rolf

[TS]

Hallo und guten Tag,

Offenbar verwendet PHP den ASR Befehl,

Das erklärt einiges.

Wenn Du auf Schieberei verzichtest und lediglich die Bit-Operatoren verwendest (& | und ~), ist alles gut. Wie Du mit 32-bit Integers aus der Präfixlänge eine Subnetzmaske machst, habe ich oben beschrieben (-pow(2, 32-$prefixlaenge)).

Das hatte ich am Anfang gemacht (siehe Posting), aber falsch herum gedacht bei der Maske. Greife ich also nochmal auf und probiere es aus.

Schaun wir also mal...

Grüße
TS

[TS]

Hallo Rolf b,

Wenn Du auf Schieberei verzichtest und lediglich die Bit-Operatoren verwendest (& | und ~), ist alles gut. Wie Du mit 32-bit Integers aus der Präfixlänge eine Subnetzmaske machst, habe ich oben beschrieben (-pow(2, 32-$prefixlaenge)).

Scheint mit pow() auch nicht zu funktionieren, da bei ip2long() und long2ip() scheinbar ein Fehler mit einem anderen ausgeglichen wird ... Aber mit

$netmask = 0xFFFFFFFF << (32 -$cidr);

scheint es wirklich zu funktionieren. Ich teste gerade noch.

Grüße
TS

[Tagwächter]

Hallo Rolf b,

Wenn Du auf Schieberei verzichtest und lediglich die Bit-Operatoren verwendest (& | und ~), ist alles gut. Wie Du mit 32-bit Integers aus der Präfixlänge eine Subnetzmaske machst, habe ich oben beschrieben (-pow(2, 32-$prefixlaenge)).

Scheint mit pow() auch nicht zu funktionieren, da bei ip2long() und long2ip() scheinbar ein Fehler mit einem anderen ausgeglichen wird ... Aber mit

$netmask = 0xFFFFFFFF << (32 -$cidr);

scheint es wirklich zu funktionieren. Ich teste gerade noch.

Und dann willst Du irre langsames und kompliziertes Zeug machen?

Da hast Du:

<?php
$netmask = 0xFFFFFFFF;
var_dump($netmask); ### float(4294967295)
$netmask = ip2long('255.255.255.255');
var_dump($netmask); ### int(-1)
$netmask = sprintf('%u', ip2long('255.255.255.255'));
var_dump($netmask); ### string(10) "4294967295"
$netmask = 1 * $netmask;# implizite Typumwandlung durch Rechenoperation
var_dump($netmask); ### float(4294967295)

Hinter den Ausgaben stehen die Ausgaben, die auf einem 32-Bit-System kommen. Auf 64-Bit-Systemen kommt:

int(4294967295)
int(4294967295)
string(10) "4294967295"
int(4294967295)

Wie auch immer. Hier steht alles, was Du brauchst ... Den Rahmen für den Check mehrerer IPs und andere Ausgaben kannst Du ja selbst machen. Oder ist das zu einfach?

[TS]

Hallo und guten Morgen,

Und dann willst Du irre langsames und kompliziertes Zeug machen?

Wie meinst Du das?

Grüße
TS

[Tagwächter]

Hallo und guten Morgen,

17:36? Hm.

Und dann willst Du irre langsames und kompliziertes Zeug machen?

Wie meinst Du das?

Naja. Für mich sieht das so aus als ob Du dann auch noch die IP-Adressen in die hexadezimale Form zwingen willst ... obwohl mit sprintf(%u, ip2long($strIP)) alles ganz einfach sein könnte.

Übrigens, Deine Aussage ...

dass die OS-Basis wichtige und einfache Dinge kann, die die Hochsprache (PHP) dann wegoperiert

... stimmt so nicht. Die Begrenzung von Integer/Long auf 2^32 ohne bzw. 2^31 mit Vorzeichen hat den Sinn, dass die Prozessoren "Integer-" bzw. "Long-Operationen" ungleich schneller durchführen als "Flieskommaoperationen". Und dafür muss der Kompiler / Interpreter eben auch solche Zahlen für den Prozessor bereitstellen, denn der bestimmt auch, ob Integer-Operationen benutzt werden. Also gibt es die Grenzen - und weil 64-Bit Prozessoren größere Integer/Long-Zahlen abkönnen als 32-Bitter eben auch andere Grenzen, welche die Kompiler / Interpreter natürlich kennen oder ermitteln können. Das Problem zieht sich über alle Programmiersprachen hin.

Es ist ergo nicht so, dass die Hochsprache (PHP) hier etwas "wegoperiert", was "die OS-Basis kann".

[Tagwächter]

Hast Du zufällig sowas vor?

[TS]

Hallo und guten Tag J.,

Hast Du zufällig sowas vor?

sieht fast so aus ;-)

Und wenn sie in fail2ban x-mal aufgetaucht ist, soll sie vollständig geblockt werden, eine Meldung abgesetzt werden, usw. Damit die iptables-Rules-Liste aber nicht über alle Grenzen wächst, soll eben zusammengefasst werden.

Außerdem sollen diverse andere Funktionen, Berichte und Views angekoppelt werden. Das ist mir als ungeübtem Shellscript-Schreiber einfach zu gefährlich mit einer Shellscript-Sammlung.

Dass sich die "klitzekleine Aufgabe" aber so ausweitet, weil scheinbar PHP (5.4.x) ungeeignet ist, habe ich nicht vorhergesehen.

Grüße
TS

[Tagwächter]

Und wenn sie in fail2ban x-mal aufgetaucht ist, soll sie vollständig geblockt werden,

Das kann fail2ban aber doch selbst:

Siehe:

/etc/fail2ban/filter.d/recidive.conf

[TS]

Hallo J.,

Und wenn sie in fail2ban x-mal aufgetaucht ist, soll sie vollständig geblockt werden,

Das kann fail2ban aber doch selbst:
Siehe:
/etc/fail2ban/filter.d/recidive.conf

DU hast da auch mal 'was ergänzendes gebastelt. Ich erinnere mich deutlich daran. Aber es sollen noch ein User-Desk dazukommen und diverse Kontroll- und Ergänzugsfunktionen. Das kann ich mit Shellscripting und/oder den eingebauten Möglichkeiten nicht abbilden.

Ich ärgere mich nur wieder mal darüber, dass die OS-Basis wichtige und einfache Dinge kann, die die Hochsprache (PHP) dann wegoperiert.

Grüße
TS

[Tagwächter]

DU hast da auch mal 'was ergänzendes gebastelt.

Aber ja doch. Das war aber bevor es den Filter recidive gab bzw. bevor ich dessen Existenz überhaupt bemerkte.

Ich ärgere mich nur wieder mal darüber, dass die OS-Basis wichtige und einfache Dinge kann, die die Hochsprache (PHP) dann wegoperiert.

Nun ja. fail2ban behandelt die IP einfach als String und rechnet auch nicht mit irgendwelchen Netzwerkmasken herum.

Der Tipp mit

sprintf( '%u', ip2long( $ip ) );

steht in der Dokumention von ip2long in beiden Beispielen drin. Und es wird auch erläutert warum das verwendet werden soll.

[TS]

Hallo J.,

Ich ärgere mich nur wieder mal darüber, dass die OS-Basis wichtige und einfache Dinge kann, die die Hochsprache (PHP) dann wegoperiert.

Nun ja. fail2ban behandelt die IP einfach als String und rechnet auch nicht mit irgendwelchen Netzwerkmasken herum.

Der Tipp mit

sprintf( '%u', ip2long( $ip ) );

steht in der Dokumention von ip2long in beiden Beispielen drin. Und es wird auch erläutert warum das verwendet werden soll.

Das mag ja sein. Aber ich muss die Ergebnismenge in PHP erzeugen, bis sie dann irgendwann mal an iptables übergeben werden soll.

Aber ich glaube, ich habe jetzt die Lücke gefunden ;-)

Ich teste noch.

Grüße
TS

[TS]

Hallo und guten Morgen J.,

Und wenn sie in fail2ban x-mal aufgetaucht ist, soll sie vollständig geblockt werden,

Das kann fail2ban aber doch selbst, siehe:
/etc/fail2ban/filter.d/recidive.conf

Ich habe das heute nacht noch eingerichtet als erste Lösung. Funktioniert auch wunderbar...

Nachdem meine PHP-Applikation nun rudimentär so schön funktioniert, wuchsen die Begehrlichkeiten doch sprunghaft.

• Registrierung von Zugriffen über verschiedene IPs aus dem gelichen Netzbereich laut IANA
• Umgang mit logrotated Files, damit keine Rotate-Lücke entsteht. Also mindestens *.log.1 und *.log müssen beide ausgewertet werden
• Bessere Verwaltung von Exclusions (obwohl ich meine, dass die mit "ignoreip" reichen sollte). Aber es sollen mehrere IPs aus unterschiedlichen Netzen ignoriert werden können. Ob fail1ban das auch kann, habe ich noch nicht rausgefunden.

Weißt Du, wie fail2ban mit logrotated Files umgeht? Wird nur das angegebene Logfile pro Filter ausgewertet, oder die unkomprimierte Logfile-Famile (also *.log.1 + *.log)?

Ich habe nach einem normalen Forum oder einer Mailingliste für fail2ban gesuscht, bin aber außer den (abgeriegelten) Wikis nicht fündig geworden. Wie kann ich da mit jemandem Kontak aufnehmen, der sich auskennt?

Grüße
TS

[Tagwächter]

Weißt Du, wie fail2ban mit logrotated Files umgeht? Wird nur das angegebene Logfile pro Filter ausgewertet, oder die unkomprimierte Logfile-Famile (also *.log.1 + *.log)?

jail.conf

[apache]
...
logpath: /etc/apache2/error.log.1
         /etc/apache2/error.log
...

bewirkt laut /var/log/fail2ban.log was Du willst:

2016-10-26 13:07:06,876 fail2ban.filter : INFO   Added logfile = /var/log/apache2/error.log.1
2016-10-26 13:07:06,880 fail2ban.filter : INFO   Added logfile = /var/log/apache2/error.log

Mit ignoreip mache es auch so.

[TS]

Hallo J.,

Weißt Du, wie fail2ban mit logrotated Files umgeht? Wird nur das angegebene Logfile pro Filter ausgewertet, oder die unkomprimierte Logfile-Famile (also *.log.1 + *.log)?

jail.conf

[apache]
...
logpath: /etc/apache2/error.log.1
         /etc/apache2/error.log
...

bewirkt laut /var/log/fail2ban.log was Du willst:

2016-10-26 13:07:06,876 fail2ban.filter : INFO   Added logfile = /var/log/apache2/error.log.1
2016-10-26 13:07:06,880 fail2ban.filter : INFO   Added logfile = /var/log/apache2/error.log

Mit ignoreip mache es auch so.

Danke J.
Dann baue ich das da noch ein und habe (hoffentlich) weitere vier Wochen Ruhe vor den Zusatzwünschen ;-)

Gibt es irgendwo (außer unter fail2ban.org) eine aussagekräftige Doku?
So wirklich alles steht da mMn nicht drin...

Grüße
TS

[Tagwächter]

Gibt es irgendwo (außer unter fail2ban.org) eine aussagekräftige Doku?
So wirklich alles steht da mMn nicht drin...

Hm. Vielleicht sollte ich mal eine solche schreiben und als Ebook raushängen. Derlei scheint auch als Werbung viel zu bringen.

[TS]

Hallo J.,

Gibt es irgendwo (außer unter fail2ban.org) eine aussagekräftige Doku?
So wirklich alles steht da mMn nicht drin...

Hm. Vielleicht sollte ich mal eine solche schreiben und als Ebook raushängen. Derlei scheint auch als Werbung viel zu bringen.

Das möchte ich fast garantieren.
Du kannst Dafür "http://tux-security.de" benutzen und dann deine Sponsoring-Werbung darauf unterbringen ;-)

ausreichend Fragen könnte ich bestimmt auch noch beisteuern. Also sollte die Anleitungsseite auf jeden Fall auch einen UCN-Bereich haben.

Und wenn Du schon mal dabei bist, könntest Du dich gelich noch mit logrotate beschäftigen und mit der PHR-GC-Konfiguration unter Debian (als Cron), die dann bitte aber auch Virtual Hosts mit eigenen Session-Verzeichnissen können muss.

Grüße
TS