0x12 = 18??? - Das (Computer-)Geek-Quiz

**dead_orc** · 10.05.2008 20:30

Ganz großer Tennis ey. Der Admin verpennts hier ne neue Frage reinzustellen!

Nehm ich halt irgendwas einfaches... öhm...

Nenne drei der häufigsten Angriffsvektoren im Bereich von Webapplikationen.

**Manni** · 10.05.2008 22:26

Zitat von dead_orc

Ganz großer Tennis ey. Der Admin verpennts hier ne neue Frage reinzustellen!

Nehm ich halt irgendwas einfaches... öhm...

Nenne drei der häufigsten Angriffsvektoren im Bereich von Webapplikationen.

Wie wäre es mit XSS, SQL-Injections und Lücken in Uploads, über die dann zum Beispiel Code hochgeladen und ausgeführt werden kann. Wobei das auch noch auf unkontrolliertes Einbinden von externem Code passt. Insgesamt natürlich vor allem die Dummheit und Nachlässigkeit der Programmierer und/oder der User.

**dead_orc** · 10.05.2008 22:32

Zitat von Manni

Wie wäre es mit XSS, SQL-Injections und Lücken in Uploads, über die dann zum Beispiel Code hochgeladen und ausgeführt werden kann. Insgessamt natürlich vor allem die Dummheit und Nachlässigkeit der Programmierer und/oder der User.

Perfekt, genau die drei Sachen wollte ich hören!

Wobei mir auch das Buzzword Buffer Overflow gereicht hätte als dritter Punkt.

Manni's turn.

**Lukas** · 12.05.2008 20:23

Zitat von dead_orc

Ganz großer Tennis ey. Der Admin verpennts hier ne neue Frage reinzustellen!

Ach scheiße, sorry

Ich hab ewig drüber nachgedacht, bin auf nichts gekommen und hab dann verpeilt, Freirunde zu posten. Tut mir leid :/

**Manni** · 12.05.2008 23:06

Mh, eine Frage zu SVG: Wie kann man in einem SVG Bild einen Link erzeugen?

**dead_orc** · 13.05.2008 09:44

Da es sich um einen W3C XML Standard handelt, vermute ich einfach mal, dass das mit XLink geht.

**Manni** · 13.05.2008 20:40

Zitat von dead_orc

Da es sich um einen W3C XML Standard handelt, vermute ich einfach mal, dass das mit XLink geht.

Das ist, naja, halb richtig. Mal schauen ob noch jemand anderes eine vollständigere Antwort gibt, ansonsten bist du ran

**Cherry** · 15.05.2008 10:17

Wie dead_orc schon sagte, mit xlink.

<a xlink:href="www.google.com" xlink:title="Google"><rect x="10" y="5" width="20" height="30" /></a>

Erzeugt ein Rechteck von 10/5 zu 30/35 als Link zu Google

**Manni** · 15.05.2008 19:38

Zitat von Cherry1

Wie dead_orc schon sagte, mit xlink.

<a xlink:href="www.google.com" xlink:title="Google"><rect x="10" y="5" width="20" height="30" /></a>

Erzeugt ein Rechteck von 10/5 zu 30/35 als Link zu Google

Jo stimmt. Im Prizip muss man das <a>-Element nicht unbedingt verwenden, aber die Spezifikation sieht es als eine Art Gruppierungselement speziell für Links an. Du bist

**Cherry** · 15.05.2008 20:20

Okay.

Wie groß ist die kleinstmöglichste Win32-PE-EXE der Welt, und welches Tricks (die Header betreffend) muss man sich dabei bedienen?

mfG Cherry

**jwiechers** · 18.05.2008 02:55

Die Frage ist so nicht direkt beantwortbar, da Windows 2000 (und, wenn ich mich nicht irre in einigen Einstellungen auch Windows 2003 Server) die Kernel32.dll nicht automatisch lädt und wir daher sicherstellen müssen, dass sie geladen wird. Weiters stellt sich die Frage ob die PE Datei noch standardkonform sein soll.

Ich hab selbst mal mit einigen Freunden versucht die kleinstmögliche PE Datei zu konstruieren und denke, dass man minimal 97 Byte braucht, unter Windows 2000 133 Byte - wenn man denn tatsächlich all die Arbeit auf sich nimmt die Import Table, die IAT und den Namen der DLL auseinanderzunehmen und in unverwendete Felder des Programms stopft.

Mal sehen ob ich mich an alles erinnere:

Ein normales, minimales C-Programm (in Richtung von int main() { return 23; } hat ungefähr 44 kB, wenn man an den Kompilierungsoptionen nicht herumspielt. Entfernt man die C Laufzeitbibliothek und das Konsolenfenster, so kommt man auf ungefähr ein kB.

Das wäre alles noch Standardkonform, aber du fragst ja nach Minima, also schauen wir uns das File Alignment an, welches, spezifikationsgemäß auf 512 gesetzt ist. Das bedeutet aber auch, dass alles zwischen Header und 0x200 mit Nullen gefüllt ist - das ist Platzverschwendung.

Wenn wir das File Alignment via dem Linker von MS auf 1 setzen, dann kommen wir auf ungefähr ein halbes Kilobyte.

So, das wird dir immer noch zu groß sein, aber das ist das Maximum was man auf dieser Ebene kann, das heißt wir gehen zur Maschinenebene über: Disassembler ausgepackt (z.B. NASM) und die MS PE Spezifikationen mit den Inhalten der Datei verglichen - alles was nicht notwendig ist fliegt raus. Am einfachsten geht das - eine Idee auf die ich leider erst später durch einen Freund gekommen bin, indem man ein kleines Programm schreibt welches schlicht alle Header-Felder durchgeht, sie mit irgendwas ersetzt und dann schaut ob das Programm das herauskommt entweder crasht oder nicht ausgibt, was es ausgeben soll. Ich hab das damals manuell gemacht ;_;.
Da wir keine Data Directories brauchen können wir diese ebenfalls rausschmeißen (NumberOfRvaAndSizes).

Dann kann man noch den MZ Header und den PE Header teilweise zusammenlegen, die dumme DOS Meldung entfernen und kommt auf ungefähr 150 Byte.

Wenn man dann noch dazu übergeht den PE Header in den optionalen Header einzubauen (was geht, da Windows zwar die Adresse des Section Headers durch Anfangsoffset des Optional Headers + SizeOfOptionalHeader ausrechnet, aber niemals die Größe des Headers selbst prüft), dann spart man sich nochmal ungefähr 53 Byte, was uns zu exakt 97 Byte bringt.

Alle Angaben ohne Gewähr, ist ne Weile her.

**Cherry** · 18.05.2008 08:05

stimmt (ich hab jetzt vergessen, dass Win2000 da anders ist, ich meinte die WinXP-Version).

Es ist also richtig.

Der Trick, von dem ich geredet habe, war eben der, die Header zusammenzulegen, wobei dann e_lfanew (MZ) und SectionAlignment (PE) zusammenfällt (beides 4, weil dann der PE Header ja auch bei Offset 4 startet).

Code:

; tiny.asm

BITS 32

;
; MZ header
;
; The only two fields that matter are e_magic and e_lfanew

mzhdr:
    dw "MZ"       ; e_magic
    dw 0          ; e_cblp UNUSED

;
; PE signature
;

pesig:
    dd "PE"       ; e_cp, e_crlc UNUSED       ; PE signature

;
; PE header
;

pehdr:
    dw 0x014C     ; e_cparhdr UNUSED          ; Machine (Intel 386)
    dw 1          ; e_minalloc UNUSED         ; NumberOfSections

;   dd 0xC3582A6A ; e_maxalloc, e_ss UNUSED   ; TimeDateStamp UNUSED

; Entry point

start:
    push byte 42
    pop eax
    ret

codesize equ $ - start

    dd 0          ; e_sp, e_csum UNUSED       ; PointerToSymbolTable UNUSED
    dd 0          ; e_ip, e_cs UNUSED         ; NumberOfSymbols UNUSED
    dw sections-opthdr ; e_lsarlc UNUSED      ; SizeOfOptionalHeader
    dw 0x103      ; e_ovno UNUSED             ; Characteristics

;
; PE optional header
;
; The debug directory size at offset 0x94 from here must be 0

filealign equ 4
sectalign equ 4   ; must be 4 because of e_lfanew

%define round(n, r) (((n+(r-1))/r)*r)

opthdr:
    dw 0x10B      ; e_res UNUSED              ; Magic (PE32)
    db 8                                      ; MajorLinkerVersion UNUSED
    db 0                                      ; MinorLinkerVersion UNUSED

;
; PE code section
;

sections:
    dd round(codesize, filealign)             ; SizeOfCode UNUSED                  ; Name UNUSED
    dd 0          ; e_oemid, e_oeminfo UNUSED ; SizeOfInitializedData UNUSED
    dd codesize   ; e_res2 UNUSED             ; SizeOfUninitializedData UNUSED     ; VirtualSize
    dd start                                  ; AddressOfEntryPoint                ; VirtualAddress
    dd codesize                               ; BaseOfCode UNUSED                  ; SizeOfRawData
    dd start                                  ; BaseOfData UNUSED                  ; PointerToRawData
    dd 0x400000                               ; ImageBase                          ; PointerToRelocations UNUSED
    dd sectalign  ; e_lfanew                  ; SectionAlignment                   ; PointerToLinenumbers UNUSED
    dd filealign                              ; FileAlignment                      ; NumberOfRelocations, NumberOfLinenumbers UNUSED
    dw 4                                      ; MajorOperatingSystemVersion UNUSED ; Characteristics UNUSED
    dw 0                                      ; MinorOperatingSystemVersion UNUSED
    dw 0                                      ; MajorImageVersion UNUSED
    dw 0                                      ; MinorImageVersion UNUSED
    dw 4                                      ; MajorSubsystemVersion
    dw 0                                      ; MinorSubsystemVersion UNUSED
    dd 0                                      ; Win32VersionValue UNUSED
    dd round(hdrsize, sectalign)+round(codesize,sectalign) ; SizeOfImage
    dd round(hdrsize, filealign)              ; SizeOfHeaders
    dd 0                                      ; CheckSum UNUSED
    db 2                                      ; Subsystem (Win32 GUI)

hdrsize equ $ - $$

filesize equ $ - $$

**jwiechers** · 18.05.2008 18:46

Es gibt mehr als einen Weg die folgende Aufgabe zu lösen, mich interessiert ein eleganter Weg, nicht die offensichtliche Brute-Force-Methode.

Um es ein wenig schwieriger zu machen hätte ich danach noch gerne die Generalisierung des Problems, wobei die Kondition, dass der Frosch immer nur auf jeder zweiten Kachel landen kann ebenfalls (als 'k') generalisiert werden sollte.

Ein kleiner Frosch springt über insgesamt 20 Kacheln von Punkt A nach B. Der kleine Frosch darf immer nur vorwärts springen und kann auch direkt von Punkt A nach Punkt B springen. Er darf natürlich auch auf jedem Feld zwischen den beiden landen, aber niemals auf zwei aufeinanderfolgenden Feldern. A und B sind in diesem Zusammenhang nicht als Felder zu rechnen. Wie viele mögliche Wege gibt es für den kleinen Frosch?

A [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] B

Und nun die tatsächliche Frage: Was ist der elegante Weg an die Zahl der Wege zu kommen?

**Crash-Override** · 18.05.2008 20:40

Und was ist jetzt die Frage?

**jwiechers** · 18.05.2008 20:57

Das steht da oben, was ist der elegante Weg - zwei Leute haben es schon rausgekriegt, wollten aber noch sehen ob es andere finden.

**DFYX** · 18.05.2008 22:43

Code:

#include <stdio.h>

u8 b = 21;
u8 k = 2;

u32 PossibleWays(u8 a)
{
  u32 result = 1;
  for(int c = a + k; c < b - k; c++)
  {
    result += PossibleWays(c);
  }
  return result;
}

int main()
{
  printf("Es gibt %d Wege von A nach B\n", PossibleWays(0));
  return 0;
}

Nicht getestet, aber sinngemäß so.

Zitat

[23:37] DFYX: Im Prinzip gibt es für den Weg von A nach B den direkten Weg und alle Wege, die über einen beliebigen Punkt C führen, der mindestens k von A und B entfernt ist, wobei für den Weg von C nach B analog zum Weg von A nach B verfahren wird
[23:37] DFYX: (Und C liegt rechts von A)

**jwiechers** · 20.05.2008 22:29

Vielleicht war die Frage etwas seltsam gestellt, aber andererseits sind einige Personen bei exakt dieser Fragestellung auf das gekommen, auf das ich hinaus wollte. DFYX Lösung ist in sofern elegant, als das sie nur korrekte Wege zählt (wobei 'fyx nochmal genau lesen sollte und seine Formel insofern modifizieren sollte, das weder A noch B Felder sind (

)), was zumindest schon mal eine Verbesserung ist, aber aufgrund der wundervollen Einfachheit der Mathematik hätte man auch auf eine andere, viel bezauberndere Lösung kommen können die sich aus der Äquivalenz der reinen Summenbildung und der Konstruktionsvorschrift der Fibonacci-Folge (Siehe hier) ergibt. Rechnet man einfach die Summe aus, so kommt man auf 17.711 Wege, welche der Frosch einschlagen kann - und welche Zahl findet sich an der Stelle F(20+2)? Genau, ebenfalls 17.711.

Um das ganze mal bildlich und nicht mit Formeln zu erklären:

Restriktion: Keine: Der Frosch darf beliebig springen.
Wenn der Frosch keine Restriktionen hat, dann ergibt sich - wie hoffentlich wirklich jedem klar ist, die Folge 2,4,8,16: 2^n.

Restriktion: Nur jedes 2. Feld darf berührt werden.
0 Felder:
A B
Der Frosch hat einen Weg. (A,B)

1 Feld:
A [ ] B
A [x] B
Der Frosch hat exakt zwei Wege, (A,B & A,1,B)

2 Felder:
A [ ] [ ] B
A [x] [ ] B
A [ ] [x] B
Der Frosch hat exakt drei Wege (A,B & A,1,B & A,2,B)

3 Felder:
A [ ] [ ] [ ] B
A [x] [ ] [x] B
A [x] [ ] [ ] B
A [ ] [x] [ ] B
A [ ] [ ] [x] B
Der Frosch hat exakt fünf Wege (A,B & A,1,3,B & A,1,B & A,2,B & A,3,B)

4 Felder:
A [ ] [ ] [ ] [ ] B
A [x] [ ] [ ] [ ] B
A [x] [ ] [x] [ ] B
A [x] [ ] [ ] [x] B
A [ ] [x] [ ] [x] B
A [ ] [x] [ ] [ ] B
A [ ] [ ] [x] [ ] B
A [ ] [ ] [ ] [x] B
Der Frosch hat exakt acht Wege (...)

5 Felder:
A [ ] [ ] [ ] [ ] [ ] B
A [x] [ ] [ ] [ ] [ ] B
A [ ] [x] [ ] [ ] [ ] B
A [ ] [ ] [x] [ ] [ ] B
A [ ] [ ] [ ] [x] [ ] B
A [ ] [ ] [ ] [ ] [x] B
A [x] [ ] [x] [ ] [x] B
A [x] [ ] [x] [ ] [ ] B
A [x] [ ] [ ] [x] [ ] B
A [x] [ ] [ ] [ ] [x] B
A [ ] [x] [ ] [ ] [ ] B
A [ ] [ ] [ ] [x] [ ] B
A [ ] [ ] [x] [ ] [x] B
Der Frosch hat exakt dreizehn Wege

Wie man sieht, etabliert sich die Fibonacci-Folge - und wie ebenfalls offensichtlich sein dürfte verändert sich dies, ändern wir den Parameter der zu überspringenden Felder. Nehmen wir an, dass der Frosch immer über mindestens zwei Felder springen muss, dann erhält man die Folge 2,3,4,6,9,13,..., bei der man nicht die beiden vorherigen Nummern addiert, sondern jeweils n-1 und n-3 addiert. Bei drei Feldern ergibt sich folgerichtig 2,3,4,5,7,10,14, also n-1 + n-4. Man setze beliebig fort. :-)

mirabile dictu!

Wenn Malu möchte, er war der erste, der drauf kam, ansonsten, freie Runde.

**malu** · 21.05.2008 13:21

Nein, danke, denn
1. bin ich bei sowas schrecklich unkreativ und
2. hab ichs hier ja nicht gepostet.

**Ineluki** · 22.05.2008 18:45

Gut, da ich ebenfalls Sephis Raetsel geloest hab (ich durfte nicht ins Forum sehen weil er schon die loesung gepostet hatte), ich einen Beweis durch vollstaendige Induktion dazu gelegt habe (wenn interesse besteht, poste ich ihn gerne) und es eine Freirunde ist, bin ich so frei, ein Raetsel zu stellen ...

Frage: Warum laeuft der folgende C Code bei echter Parallelisierung auf einem Zwei-Prozessor-System mit Shared Memory unterschiedlich schnell, je nachdem, wie die Schleife (z.B. vom Programmierer) auf die Prozessoren aufgeteilt wird ?

Code:

double A[SomeBigNum];
...
int i;
for ( i=0; i<SomeBigNum; ++i )
  A[i] += 1;

Tipp: Wenn Prozessor1 alle geraden Indizes und Prozessor2 die ungeraden Indizes bearbeitet anstatt Prozessor1 die Indizes von 0 bis SomeBigNum/2-1 und Prozessor2 von SomeBigNum/2 bis SomeBigNum-1 ist der Code um teilweise mehr als Faktor 10 langsamer.

Tipp 2: Das selbe Problem aus einer aehnlichen Ursache kann auch bei seriellem Single-Prozessor-Code auftreten, wenn man mit zweidimensionalen Arrays arbeitet und die beiden Schleifen-Indizes vertauscht.

**Brainstar** · 23.05.2008 10:43

Größere Sprünge bei der Adresse von A?

Thema: 0x12 = 18??? - Das (Computer-)Geek-Quiz

Themen-Optionen

Anzeige

Berechtigungen