Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 3 Implementierung
Hey,
ich hab folgende Frage, muessen wir die Aufgabe genau so implementieren wie in der Uebung?
Oder reicht es wenn meine Implementierung das Verhalten in den man-Pages aufweist?
Weil mir dieser Algorithmus alles andere als geheuer ist. Mal abgesehen davon dass er wie wir schon wissen ineffizient ist, weil er Speicherbloecke nicht mehr verschmilzt, was mir eigentlich egal ist.
Aber mein Hauptproblem ist dass wenn ich mir den Algorithmus schon nur anschau gehn bei mir schon alle Alarmsignale an. Jedem der sich auch nur irgendwie mit Computersicherheit auskennt, sollten sich an dem Punkt alle Haare aufstellen, die Schuhe ausziehn und die Zehennaegel sich nach oben rollen. Und das bringt man bei, und Leute wundern sich warum niemand sicheren Code schreiben kann …
Da waer zum Beispiel erstens die Tatsache dass der User mit free richtig schoen faxen machen kann, ich kann in einer Sekunde Code schreiben, der allen Speicher voellig zerstoert plus ich bin mir ziemlich sicher dass ich eure Funktionen ziemlich schnell zum abschmieren krieg. Das mag jetzt ignoriert werden mit selber schuld wenn einem dann der Prozess um die Ohren fliegt, aber in dem Moment wo dann mehr als eine Datei unser Ding zur Speicherverwaltung verwenden soll, da kann man die Ausrede nicht mehr bringen, weil dann die Dummheit eines Programmierers alle anderen Anwendungen auch killt(und des is noch Best-case). Geschweige denn ein sehr schlauer Programmierer, der das absichtlich macht, um schoene Dinge in andere Prozesse zu injekten.
Oder das Ding mit den Metadaten in unserem Speichersegment facepalm, nein bitte bitte nicht. Ich kann durch in den Speicher schreiben daten ueberschreiben, die Informationen ueber unseren Speicher halten. Wirklich? Klingt des nicht irgendwie schon schlecht?
Ok, ich bin jetzt erstmal fertig mit meinem rant, wer will, ich hab noch mehr wo das herkam ;).
Auch wenn du meinst es besser zu wissen bzw. dir die Vereinfachungen die bei Aufgabenstellungen gemacht werden nicht passen, rate ich dir trotzdem, dich an die Aufgabenstellung zu halten.
SP1 ist eine Vorlesung für das 2. Semester, da muss man die Aufgabenstellung nunmal etwas einschränken, auch wenn die Software so vielleicht nicht flächendeckend verwendet werden sollte.
Wenn du dich aber nicht an die Aufgabenstellung hälst, z.B. durch Implementierung nicht gefordeter Komponenten, etc. musst du mit Punktabzug rechnen.
Deswegen die Frage ob es auch reicht wenn ich es anders implementiere und es die man-Page erfuellt.
Edit: Ausserdem ist Vorlesung im 2ten september keine entschuldigung fuer schlechte praktiken. Das sollte man ja eigentlich lernen, gut zu programmieren. Man geht auch nicht her und bringt in java bei es waere super, man nennt seine Variablen a, b, c, seine Methoden funktion1, funktion2, funktion3, etc. Weil es nicht getan werden sollte. Oder in C sollte man strcpy benutzen ohne Laengencheck. Es gibt einfach Dinge die niemals getan werden sollten (es sei denn es gibt einen sehr SEHR guten grund es doch zu tun). Ich denke die Uebungen sollten das reflektieren, v.a. da man auf der anderen Hand punkte abzieht fuer mehr globale Variablen als noetig, also offensichtlich das aehnlich sieht. Ich finde das in diesem Fall einfach inkonsequent. Und das hat auch nichts mit besserwissen zu tun, das sollte meiner Meinung auch einfach mal gesagt werden, wie wenn Fehler in der Aufgabenstellung sind.
Mir drängt sich die Frage auf, wie du es denn umsetzen willst. Am einfachsten und schnellsten ist die Umsetzung, wie sie in der Übung besprochen wurde. Und eine Implementierung mit beispielsweise einer Tabelle zur Verwaltung der Freispeicherplätze erfüllt die Aufgabenstellung eindeutig nicht.
Warum sollte eine Tabelle die aufgabenstellung nicht erfuellen? Ich kann die Aufgabenstellung so interpretieren dass “Die Listenelemente die die Groesse des verwalteten Speicherbereichs beinhalten werden am Anfang des dazugehoerigen Speicherbereichs abgelegt” bedeutet ich reserviere mir vor meinem statischen Speicher Platz fuer meine Tabelle (Eine sequentielle LinkedList, kann ich so interpretieren, diese hat halt dann nur beschraenkte groesse, ist aber auch auf keinen fall ineffizienter als wenn irgendwann der ganze speicher aus 1 byte groessen bloecken besteht, natuerlich absolutes extrem, aber dazu kann es fuehren). Dann kann ich bei meinen free-Aufrufen sehen, ob der Pointer jetzt auf einen Speicherblock zeigt, der tatsaechlich allocated wurde. Und dann wird auch kein Speicherplatz ge-free-t der nie alloziert wurde, oder an adressen ge-free-t die mitten in einem Speicherblock liegen. Dann kann ich diese Tabelle Page-guarden, und ich kann auch nicht mehr den Speicher ueberschreiben, der Info ueber den Speicher enthaelt. Das waere zumindest ein Anfang.
Nö. Das „echte“ [m]malloc[/m] macht das auch nicht arg anders, deswegen stürzt ja z.B. [m]free[/m] mit schlimmen Verwünschungen ab, wenn du über das Ende des Blocks hinausgeschrieben hast und dann free drauf aufrufst. So lange du Speicherverwaltung im Userspace machst, hat das Benutzerprogramm immer die Möglichkeit, Strukturen kaputtzuschießen, egal wo die liegen.
Dank virtuellem Adressraum passiert dem Rest vom System dabei aber nichts. Und das Programm selber sollte sich durch robuste Programmierung und Validierung von Benutzereingaben sowieso vor Pufferüberläufen u.ä. schützen.
5 Likes
[quote=tempus maximus]Dann kann ich diese Tabelle Page-guarden, und ich kann auch nicht mehr den Speicher ueberschreiben, der Info ueber den Speicher enthaelt.[/quote]Nein, kannst du nicht, denn das würde Betriebssystemunterstützung erfordern und deswegen erzwingen, dass [m]malloc(3)[/m] ein System Call wäre. Natürlich kannst du die Metadaten irgendwo in deinem Adressraum verschieben und verstecken, das wird aber niemanden, der das mit voller Absicht versucht, daran hintern dir diese Metainfos zu zerschießen, wenn er denn möchte. Ob du jetzt also deine Metadaten direkt vor dem Block ablegst, oder irgendwo sonst im Adressraum macht sicherheitstechnisch genau gar keinen Unterschied.
3 Likes
Hast du verstanden, dass es bei der Halde nur darum geht, Speicher, der eh nur zum aktuellen Prozess gehört in kleinen Einheiten zu verwalten?
Edit: Ergänzung: Die Frage, wie ein Prozess vom Betriebsystem Speicher anfordert wird bei der halde nicht betrachtet.
1 Like
Ja.
ict hat es schon gesagt, aber ich wiederhole das nochmal weil es wichtig ist. Prozesse laufen auf GNU/Linux (und den meisten anderen Systemen) in getrennten Adressräumen. Ein Prozes kann den Speicher eines anderen nicht direkt beeinflussen (es sei denn es ist gewollt, Stichwort: Shared Memory). Eine „kaputte“ [m]malloc[/m]-Implentierung beeinflusst also nur den Prozess selbst, und keine anderen.
Es stimmt, dass in der Übung nicht extra auf die Problematik der gemeinsamen Speicherung von Metadadaten und Nutzdaten eingegangen wird (Stichwort: Double Free bei [m]malloc()[/m]). Allerdings wird das nur bei inkorrekter Nutzung von C (fehlende Längenabfragen, Bufferoverflow, etc.) ein Problem. Und wie neverpanic schon schrieb, lässt sich das nicht vermeiden. System Calls als Lösung wären deutlich langsamer.
Sobald ein Angreifer Daten im Programm überschreiben kann, hast du ein Problem. Aber selbst wenn es möglich wäre, [m]malloc()[/m] „sicher“ zu implementieren, hat dein Programm ja selber auch Nutzdaten, die der Angreifer überschreiben kann (z.B. [m]authenticated = 0[/m]). Durch einen Überlauf kann er dann z.B. diese Werte manipulieren. Deswegen ist es in C besonders wichtig korrekte Programme zu schreiben, die nicht für Pufferüberläufe, Integerüberläufe, etc. anfällig sind.
4 Likes
Immer her damit! 
Deine bisherigen Kritikpunkte haben allesamt auf der Grundannahme basiert, dass wir in Aufgabe 3 eine Betriebssystemkomponente bauen, die für alle Prozesse zentral Speicher verwaltet. Diese Annahme ist allerdings, wie bereits oben festgestellt, völlig falsch: Wir bauen eine Programmbibliothek, die feingranular Speicher für einen isolierten Prozess verwaltet.
Also bin ich mal gespannt, was du noch für Pömpeleien auf Lager hast. 
Ich hab ganz und gar nicht den Eindruck, in zwei Semestern SP schlechte Praktiken beigebracht bekommen zu haben.
Im Gegenteil, SP war wahrscheinlich die Veranstaltung, wo jenseits des Schreibens von lauffähigem Code am meisten auf Best-Practices und sauberen Stil eingegangen wurde. Das mag aber von Übungsleiter zu Übungsleiter verschieden sein.
Was die Sicherheit angeht: Wart mal auf SP2, da wird auf Buffer Overflows etc. noch genauer eingegangen ;).
Dass diese Aufgabe in keinerlei Hinsicht den Anspruch hat, ein der Standardbibliothek ebenbürtiges [m]malloc()[/m] zu bauen, sollte inzwischen klar geworden sein. Es ist eben eine starke Vereinfachung die auch für Leute, die seit einem Monat C programmieren, machbar sein muss.
1 Like
Also, nach 2 Tagen Pause und erneutem Durchlesen ist mein erster Post durchaus sehr emotional und provokativ.
Das war zu keinem Zeitpunkt meine Absicht, da es mir hier wirklich um eine sinnvolle Loesung der Aufgabe geht,
auch wenn das vllt. erst einmal nicht offensichtlich ist ;).
Aber ich habe auch einige Dinge zu dem Thema zu sagen:
Ich habe offensichtlich eine Fehlannahme gemacht die mir nicht bewusst war, bevor ich die ganzen Kommentare ueber Adressraeume gelesen habe. Ich bin davon ausgegangen dass die hier gemachte Implementierung als Ziel hatte als eine dynamisch verlinkte Klassenbibliothek darzustellen. Daher waren meine urspruenglichen Punkte mit Programmen die andere Programme zum Absturz bringen aus meiner Sicht durchaus angebracht, nur mit einer statisch verlinkten Bibliothek sind diese natuerlich alles andere als zutreffend. Daher entschuldige ich mich hier fuer das Missverstaendnis.
Ich bin immer noch der Meinung dass auch ohne Betriebssystem unterstuetzung durch Page-Protection meine Implementierung deutliche Vorteile fuer den normalen Programmierer hat, und zwar aus mehreren Gruenden.
Erstens ist da die Tatsache dass die meisten Speicherkorruptionen durch Ueberschreiben von Speichergrenzen passieren, und nur selten vor den zugewiesenen Speicher geschrieben wird. Daher haette meine Implementierung zur Folge, dass sehr haeufige Probleme von Overflows keine Abstuerze mehr verursachen, und die Speicherverwaltung in diesem Fall unabhaengig von den falschen Daten im Speicher trotzdem korrekt laeuft. Und in dem Fall dass der Programmierer solchen Mist baut, dass des ganze in den Stack ueberlaueft, ist ihm sowieso nicht mehr zu helfen.
Zweitens, damit zusammenhaengend, finde ich dass bei einem Programmierfehler den der Programmierer macht, es besser ist wenn die Speicherverwaltung ohne Nebeneffekte funktioniert, und nur die Daten selber aber nicht das Speicherlayout korrumpiert sind. Das hat mehrere Vorteile, der Programmierer kann Tests auf den Daten durchfuehren, das ganze noch loggen, und dann selbst beenden z.b. wo er andernfalls natuerlich SIGSEGV abfangen kann, aber das hilft auch nicht mehr wirklich. Damit hat der Programmierer die volle Kontrolle darueber was bei einem solchen Fehler zu tun ist, ohne sich um unerklaerlich abstuerzende Prozesse kuemmern zu muessen.
Und drittens finde ich es durchaus auch dadurch sinnvoller dass die Speicherverwaltung tatsaechliches Wissen darueber hat, ob und welchen Speicher sie jetzt vergeben hat, ohne den allokierten Speicher dann zu vergessen. Dass kann wie gesagt auch sehr einfach dann das problem von falschen frees loesen. (z.B. auf Pointer die man irgendwann aus Versehen inkrementiert hat.)
Zusammenfassend finde ich daher dass meine Implementierung durchaus nicht sicher ist (sein kann, sollte zumindest schwierig sein ohne OS-Unterstuetzung), aber sie den Vorteil hat, zwar mutwillige Eingriffe nicht beeinflusst, aber typische Programmierfehler verhindert, bzw. weniger schwerwiegend und unnachvollziehbar macht.
Um an den Beitrag von F30 anzuknüpfen:
Hallo, hier bin ich, der Typ von Informatik-Student, der sich erst seit einem Monat mit C-Programmierung beschäftigt.
Hab mir hier den Thread durchgelesen um ein paar Infos über Aufgabe 3 zu erhaschen, um hoffentlich ein einigermaßen funktionierendes Programm abliefern zu können.
Aufgrund meines absoluten Anfängerdaseins finde ich jegliche Vereinfachung und Einschränkung echt gut, auch wenn ich deswegen auf praxisgerechte Anwendungen verzichten muss.
Ich versteh es aber auch, dass Profis bei solchen Sachen nur mit dem Kopf schütteln. Ist für mich trotzdem umso besser, durch die Diskussionen kann ich ja immerhin was dazu lernen! (Auch wenn hier die Beiträge von tempus maximus ordentlich auseinander genommen werden xD )
Damit auch mal ein Danke an tempus maximus für diesen Thread 
Also an alle Leute, die sich aufgrund der Einschränkungen und der scheinbar stupiden Aufgabenstellung verarscht fühlen:
Denkt bitte auch mal an die Anfänger unter uns. Die Aufgaben sind nur so gemacht damit auch wir ne Chanche haben 
Auch im Fall einer dynamisch gebundenen Bibliothek sind die Adressräume aller Prozesse strikt voneinander isoliert. Die dynamischen Daten, die die Bibliothek hält, existieren pro Prozess, nicht einmal global.
Deine Argumente für eine Trennung von Benutzer- und Verwaltungsdaten sind nachvollziehbar. Ich denke aber, im Endeffekt hat man immer einen Trade-Off zwischen Effizienz und Fehlertoleranz. Im Falle von C steht in den allermeisten Fällen die Effizienz klar im Vordergrund. Und das hat auch durchaus seinen Sinn: Wenn man als Primärziel die Auswirkungen von Fehlern minimieren will, sollte man von vornherein eine typsichere Programmiersprache wählen.
1 Like
@ Airhardt:
-
Meines Verstaendnisses nach sind die Daten dann doch in den Heappages der Bibliothek gespeichert, und diese sind global einmalig. Jetzt wo ich drueber nachdenke koennten da dann je nach OS Probleme mit dem zugriff entstehen, aber die Daten sind doch erst mal einmalig im Prozessraum der Bibliothek, oder hab ich das falsch verstanden? Es wuerden ja alle Prozesse auf den Speicher in der Bibliothek zugreifen, die Bibliothek wuerde den Speicher ja nicht im jeweiligen Heap der Prozesse anlegen.
-
Zu dem Trade-Off: natuerlich ist der immer da, und der Hauptgrund fuer die Verwendung von C ist ja die Hardwarenaehe und gewichtung auf effizienz. Das ist natuerlich klar. Aber ich sehe in dem Beispiel die Einbussen der Effizienz nicht die man fuer die Argumentation mit Trade-off braucht. Meiner Meinung nach wuerden meine Aenderungen doch die Effizienz nicht senken, aber die Fehlertoleranz erhoehen. Das ist nicht wirklich ein Trade-off ;).
@Sp1ke: Erstmal danke zurueck
Mir ist bewusst dass hier auch sehr viele Anfaenger sind die noch nie C programmiert haben. Ich wollte auch nicht irgendwie sagen dass meine Loesung jetzt unbedingt musterloesung fuer alle sein soll. Meine Frage war mehr ob ich des auf meine Art implementieren kann, ohne Punkte abgezogen zu kriegen, da sie mir persoenlich sehr viel einleuchtender erscheint. Aber mir ist klar dass das erstmal sehr einschuechternd wirken kann. Aber ich kann dir verraten, C ist gar nicht so schwer wies auf den ersten Einblick erscheint, und ich bin sicherlich alles andere als ein Profi.
Es gibt keine „Pages der Bibliothek“. Wenn ein Programm zum Laufen eine dynamische Bibliothek braucht, so wird die einfach geladen und mit in den Adressraum des Prozesses eingeblendet (wenn es eine beliebte Bibliothek wie die libc ist und sie schon von für einen anderen Prozess geladen wurde so existiert der (unveränderliche) Code der Bibliothek nur ein mal physikalisch im Hauptspeicher und wird für jeden Prozess eingeblendet).
Was die Bibliothek dann aber im Kontext des Prozesses tut (z.B. Speicher vom Betriebssystem anfordern und den in kleinen Häppchen an Aufrufer verteilen) läuft rein im Adressraum des Prozesses ab und hat keinen Einfluss auf andere „Benutzer“ der Bibliothek. Ausnahmen gibt es nur, wenn dieses Verhalten explizit gewünscht ist (Stichwort Kommunikation über shared memory).
Sonst noch zum Topic: Meiner Meinung nach ist es sogar besser, wenn einem das ganze Ding sofort um die Ohren fliegt, sobald man über seinen reservierten Speicher hinausschreibt. Lieber so als dass es nach Jahren beim Kunden plötzlich abstürzt, weil sich inzwischen intern was an der malloc-Implementierung geändert hat oder man durch den 32/64-bit-Umstieg jetzt noch weiter über das Ende hinausschreibt und Nutzdaten kaputtmacht.
1 Like
Zwei Dinge, die mir dazu spontan einfallen:
- Eine separate Tabelle mit statischer Größe würde es nicht ohne Weiteres erlauben, den Heap beliebig dynamisch zu vergrößern bzw. zu verkleinern. Du bräuchtest dann schon sowas wie eine verkettete Liste von Tabellen.
- Für das Page-Guarding brauchst du pro Allokation/Freigabe zwei Systemaufrufe.
Wobei die Vereinfachung sich vor allem auf die Effizienz bezieht (schnelle Suche und Verschmelzen). Prinzipiell funktioniert ein normales [m]malloc()[/m] genauso; inklusive der Sicherheitsprobleme (wobei da in letzter Zeit einiges verbessert wurde).
Wie ict schon schrieb, ist es nicht schlecht, dass solch eine falsche Nutzung zu Abstürzen führt. So fallen Fehler deutlich früher auf. Denn das problematische hier ist ja nicht zwangsweise, dass die [m]malloc()[/m]-Datenstrukturen zerstört werden, sondern es können ja auch die Nutzdaten des Programms überschrieben werden. Und sowas möchte man natürlich so schnell wie möglich entdecken. [m]malloc()[/m] verhindert durch ein paar Überprüfungen, dass die Überläufe einfach durch Angreifer ausgenutzt werden können (perfekten Schutz gibt es hier aber natürlich nicht).
Das verhindert schon das Betriebssystem für dich.
Siehe oben. Ich als Programmierer will eigentlich solche Fehler so schnell wie möglich finden. Und die einzige sinnvolle Aktion bei einem solchen Speicherfehler ist eigentlich das Program mit einem Speicherabzug (core) zum Debuggen zu beenden, da du ja nicht wissen kannst was noch alles kaputt gegangen ist und die Fehlersuche da IMHO erstmal das wichtigste ist.
Das wird schon vom [m]malloc()[/m] geprüft - und auch unsere Implementierung macht das (mit MAGIC). Natürlich ist das von einem Angreifer manipulierbar, aber das ist kein Argument bei einen versehentlichen Überlauf.
Siehe oben, die halde erfüllt diese Bedingungen eigentlich schon (natürlich kann man da noch deutlich mehr machen, aber für das meiste reicht MAGIC eigentlich schon aus).
Was Effizienz angeht, ist eine verbesserten Lösung auf jeden Fall schön und wenn du das korrekt implementierst (und am besten auch dokumentierst), hat dein Tutor da auch sicher nichts dagegen (solange er keine Fehler suchen muss ;-)). Die Sicherheitsaspekte lassen sich nicht wirklich lösen und deswegen solltest du da nichts anderes probieren.
1 Like
Heap-Vergroesserung: seh ich ein, wuerde denk ich aber eher die route ueber memcpy und mehr platz fuer die tabelle waehlen (jaja, effizienz, ich weiss)
Heap-Verkleinerung: ??? ich hab halt einfach mehr freien Platz in meiner Tabelle weil Eintraege im vorher belegten Platz geloescht werden.
System-calls: hatten wir ja schon abgeschrieben, da sie offensichtlich nicht erwuenscht sind.
@rudis, ict:
Erstmal danke dass du des nochmal erklaert hast es scheint ich hatte das tatsaechlich falsch verstanden, und dafuer danke.
Aber zu den Abstuerzen: glaub mir, ich waere der erste der vor Dankbarkeit auf die Knie sinkt, wenn sich malloc so verhalten wuerde. Leider tut es das aber ja nicht. Es duempelt in diesem undefinierten Zustand rum(um die Manpages zu zitieren), bis es im best-case bei der Speicherfreigabe abstuerzt, und leider aber im worst-case ja 3000 code-zeilen weiter bei etwas was nichts mit unserem Problem zu tun hat. Wenn malloc, free, etc, in dem Moment wo eine solche Verletzung passiert in einen Zustand versetzt wuerden wo dann der naechste Aufruf abstuerzt waere das toll, da man dann genau weiss wo der fehler zu suchen ist.
Aber ich persoenlich wuerde definites Verhalten dass nur den Benutzerspeicher korrumpiert, zufaellig undefiniertem ( lol) Verhalten, dass an den unpassendsten Stellen abstuerzen kann, jederzeit vorziehen, einfach um Sicherheit zu haben, dass wenn mein momentaner Code-Block in sich korrekt ist, er auch sicher problemlos durchlaeuft. Mir ist aber klar dass das wieder Einschraenkungen der Effizienz nach sich zieht und damit nicht immer erwuenscht ist. Aber ich wuerde da dann fuer meins halt so argumentieren dass ich sage, wenn man volle Effizienz haben will, kann man normales malloc verwenden und meins waere dafuer weniger effizient aber dafuer etwas stabiler.
Das mit dem in den Stack ueberlaufen war eben genau so gemeint dass in dem Moment egal ist, was die Bibliothek macht, weil einem des Programm eh schon um die Ohren fliegt.
Das Problem ist aber ja dass alles was nicht MAGIC ist als Pointer interpretiert wird, da wir das ganze im next-Feld speichern.
Ausserdem hat die Implementierung meiner Meinung nach eben kein Wissen darueber welchen Speicher sie vergeben hat. Alles was sie kann ist dir im Nachhinein sagen ob sie den Speicher den du ihr gibst vergeben hat, aber nicht welchen sonst noch, wieviel, etc.
Wie ja Airhardt schon gesagt ist von der Effizienz her meine Implementierung auch nicht besser, und in manchen faellen auch schlechter, aber sie erscheint mir persoenlich einfach als logischer (naheliegender). Zaehlt das? Ich wuerde sie natuerlich dann auch dokumentieren da ich die Standard-route nicht nehme.