Muen Separation Kernel

[dsar]

• 

.

[cdimauro]

• 

Ma non sempre è possibile prevederli. Per questo motivo ho lavorato a una nuova tecnologia per accelerare in hardware il controllo dei bound; a breve sottoporrò il draft al comitato per i brevetti, e poi vediamo cosa mi diranno.

Comunque ADA è troppo complesso come linguaggio. La sintassi, da pascaliano, mi piace molto, ma se il linguaggio diventa troppo grande la facilità di scrittura del codice tipica di Pascal & co. va a farsi benedire, e non mi piace affatto.

[TheKaneB]

• 

Vorrei ricordare che questo kernel fa "Muuuuueen". Coincidenze? Io non credo

[cdimauro]

• 

Ma non sempre è possibile prevederli.

Dipende, con il range type (bounded) esempi classici che delegano il range checking in runtime possono essere controllati in compile time, per esempio: buffer[f()]; il ritorno di f() deve essere lo stesso range type che utilizza l'array del tipo buffer. Andando sul generale non puoi iterare quel buffer con un indice che non è dichiarato dello stesso range type. Se l'array viene dichiarato con un tipo range bounded, il type checking implica il range checking.

Chiaro.

Il range checking avviene per gli unbounded range, in cui il tipo range è conosciuto solo durante il runtime (ma nel mission critical non si usano mai). Il range checking di Ada in compile time si comporta molto bene in questi casi, soprattutto quando l'array non è guarded nei cicli (for i in buffer'Range), in particolare nei cicli generici non ti permette di accedere ad un array se l'index non è controllato nella condizione.
Onestamente non ho trovato casi in cui un unbounded range non venisse catchato in compile time, sicuramente saranno casi eccessivamente complicati.. ma qui ci vuole un po' di software engineering e buon senso, casi così delicati vanno trattati con estrema semplicità per essere il più possibile padroneggiati. In ogni caso c'è il bounds checking in runtime, che protegge i casi in cui il guard sull'array non può essere garantito.

E' troppo pesante. Per questo motivo sono state sviluppate soluzioni, anche hardware, per evitarlo. Ad esempio Intel ha tirato fuori di recente la tecnologia MPX allo scopo (un altro utile link che ne parla è questo), che sarà disponibile nei prossimi processori. Ma c'è parecchio fermento, e si trovano diverse altre soluzioni o ricerche in merito. Qui trovi altra roba.

Le motivazioni sono molto semplici: si tratta di problematiche molto comuni e frequenti, e per le quali c'è forte richiesta (ma non posso dire altro, mi spiace) di tecnologie per la loro accelerazione in hardware.

Il vero problema comunque sono gli array dinamici, che oltre ad essere pericolosi per la sicurezza (buffer overflow, il resize non è altro che un free()/malloc() quindi tutti i reference diventano dangling pointer, etc) offre delle pessime performance se fai tantissime operazioni di modifica.

Esistono delle politiche per ridurre l'impatto di queste operazioni. O... altro, ma anche di questo non posso parlarne per adesso.

Morale della favola, evitare gli array dinamici ed utilizzare solo ed esclusivamente strutture dati. Questo è uno dei motivi per cui Wirth non implementò mai gli array dinamici nei suoi linguaggi.

Non sono d'accordo perché sono strumenti molto utili.

Tra l'altro con tecnologia adeguata si possono gestire in scioltezza e riducendo al minimo problematiche di robustezza e sicurezza.

Questo è anche il motivo per cui ho speso un po' di mesi per sviluppare una mia idea che mi trascinavo da anni: dimostrare che si può ottenere bound checking in hardware a un costo minimo sia a livello implementativo sia, soprattutto, a runtime. Fortunatamente dove lavoro adesso ho avuto la possibilità di svilupparla e perfezionarla ulteriormente, ma soprattutto c'è la concreta possibilità di vederla implementata su silicio (SE l'idea piacerà, e passerà poi tutta la trafila burocratica, che purtroppo è lunghetta).

Ma non sempre è possibile prevederli. Per questo motivo ho lavorato a una nuova tecnologia per accelerare in hardware il controllo dei bound;

mi sa che non sei il primo ad averci pensato, anche se in quel caso non ne e' valsa la candela: idee varie in OpenRISC!

Non conosco OpenRISC e come abbiano affrontato il problema, ma certamente non sono affatto l'unico ad averci pensato. C'è parecchia letteratura in merito, progetti, e... richieste di avere soluzioni efficienti (e che non penalizzino troppo le prestazioni). Se Intel ha sviluppato MPX, non l'ha fatto certo per caso.

esattamente cosa presenti ?

Mi spiace, ma a questo stadio non posso rilasciare alcuna informazione in merito. L'unica cosa che posso dirti è che si tratta di un'intera tecnologia che aiuta a risolvere o limitare fortemente le problematiche di bound-checking, protezione dei buffer (anche di sottoinsiemi/slice di buffer esistenti), e dangling-pointer.

E' una soluzione hardware che ha un impatto trascurabile a runtime, al contrario di altre tecnologie.

hai un nodello HDL ?

No, nessun modello HDL: lo sai che le mie conoscenze in merito sono nulle.

Al momento ho scritto un lunghissimo draft che espone tutti i dettagli, dall'implementazione all'interno di un processore fino all'applicazione che esegue il codice, con l'analisi di diversi casi d'uso e comparazione con tecnologie esistenti e concorrenti (MPX è una di esse, ma ce ne sono altre, anche in forma di sola idea interna). Ma devo ridurre notevolmente questo draft, perché per sottometterlo alla commissione brevetti il testo deve occupare al massimo un paio di paginette, e scritte in maniera quanto più chiara e intelligibile possibile.

Se dovesse andare bene, io mi fermerò qui. Al massimo sarei chiamato come consulente per la scrittura del brevetto (che viene realizzata da gente che lavora in questo campo, inclusi legali ovviamente), e forse per discutere qualcosa riguardo all'implementazione su silicio (ma ne dubito, perché quegli ingegneri non ne avranno sicuramente bisogno).

Non so se ti rendi conto dell'idea totalmente insana, ci metteresti due/tre mesi per finire di compilarlo

per questa porcata lavoro sotto QEMU/MIPS su un muletto di ordine almeno i2
fossi matto ad usare un SoC a 800Mhz che performa meno di un P3
pero' anche cosi' il cross compilare e' un bel macello, e metterlo a posto anche peggio

in compenso per PowerPC si trovano bootstrap (l'ho fatto, funge)
e anche per ARM c'e' qualcosa (non l'ho provato di persona)

Alla fine emuli i MIPS con gli x86, eh! Ma lasciali perdere e dedicati direttamente a questi ultimi.

[cdimauro]

• 

Alla fine emuli i MIPS con gli x86, eh! Ma lasciali perdere e dedicati direttamente a questi ultimi.

per forza, non ho abbastanza quattrini per comprare hw + carrozzato, volendo dalla Cina ci sarebbe pure qualcosa di + potente della + potente CPU mips che ho in casa, un R16K a 800Mhz, che non accendo quasi masi, si succhia 600Watt e' un 4 CPU.

mi costa di meno usare un muletto intel per QEMU/MIPS-catalyst (che crede di fare compilazione nativa)
Vedremo con Edison, per ora non c'e' alcun rimpiazzo, da parte mia, per i SoC MIPS
in compenso ho definitivamente abbandonato PowerPC: Cerbero, di cui vedi le foto nell'altro thread e' l'ultimo progetto, poi metto la parola fine.
E pure sulle HP.

Uno in meno. Quando smetterai con MIPS stapperemo una bottiglia di spumante.

[cdimauro]

• 

Ne resterà soltanto uno.

[cdimauro]

• 

Morale della favola, evitare gli array dinamici ed utilizzare solo ed esclusivamente strutture dati. Questo è uno dei motivi per cui Wirth non implementò mai gli array dinamici nei suoi linguaggi.

Non sono d'accordo perché sono strumenti molto utili.

Per esempio? Allargare l'array di una hash table

E' un ottimo esempio, visto che si tratta di un strumento molto utilizzato. Se prendiamo Python, ad esempio, la virtual machine è permeata sull'utilizzo di oggetti PyDictObject, che sono rappresentati in questo modo:

Codice: [Seleziona]

typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;  /* # Active + # Dummy */
    Py_ssize_t ma_used;  /* # Active */

    /* The table contains ma_mask + 1 slots, and that's a power of 2.
     * We store the mask instead of the size because the mask is more
     * frequently needed.
     */
    Py_ssize_t ma_mask;

    /* ma_table points to ma_smalltable for small tables, else to
     * additional malloc'ed memory.  ma_table is never NULL!  This rule
     * saves repeated runtime null-tests in the workhorse getitem and
     * setitem calls.
     */
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};Penso che l'utilizzo sia abbastanza chiaro: se a un certo punto il numero di entry allocate predefinitamente non sarà più sufficiente, ma_table verrà "allungato" (o ridotto) a seconda dell'esigenza.

Puoi fornire un'implementazione che sia più robusta e altrettanto efficiente?

od avere stringhe di larghezza infinitamente arbitraria?

Non è questo che genera il problema, ma se le stringhe sono mutabili. Ma ne hai parlato dopo.

Il primo l'ho sempre reputato un aborto computazionale,

Sarà un aborto, ma funziona benissimo e garantisce ottime prestazioni. Considerato quanto sia utilizzato un dizionario (hash table / map) in Python, puoi immaginare quanto sia stato ottimizzato nel tempo questo strumento / struttura dati, e quella esposta sopra rimane lo stato dell'arte (almeno per CPython). Ma, di nuovo: esiste un'implementazione più robusta e che mantenga almeno la stessa efficienza?

il secondo non ne vale assolutamente la pena ed è pessimizzante a mai finire, potrei accettarlo solo per stringhe che poi non verranno più toccate.

In Python le stringhe sono "illimitate" e immutabili, anche se internamente la virtual machine prevede delle specifiche ottimizzazioni in casi particolari, per cui una stringa può venire modificata "in-place".

Ormai sono abituato a ragionare con chunk di dati (con possibilità di essere cachati per velocizzare le operazioni) e mi trovo non bene ma benissimo.

Prova a generare in maniera efficiente una pagina web. Se non ricorri a un oggetto StringBuilder / StringIO / buffer che si allunga a dismisura, i tempi di generazione della pagina saranno estremamente elevati.

Come lo risolvi diversamente, e in maniera più "sicura", questo problema?

Dai poi un'occhiata ai principali software che garantiscono (o cercano di farlo) un security by design, nessuno di loro utilizza array allocati dinamicamente.

Non è il mio campo, per cui non ne conosco. Ma stiamo parlando di casi molto particolari nel panorama attuale.

Lasciando perdere poi il problema sicurezza e inadeguatezza per i dati, il fatto che un puntatore possa puntare a qualcosa di diverso da record/struct/class rende lento e complesso il garbage collector di oltre il 50%, ci sono almeno una quindicina di block descriptor in più solo per gestire il caso degli array allocati dinamicamente, contro un solo block descriptor per record/struct/class, poi la situazione peggiora se un puntatore può puntare "in mezzo" all'array ma fortunatamente questo è un problema dei linguaggi C/C++ . (Ok questo è più un problema implementativo che non riguarda il programmatore/utilizzatore).

Purtroppo è un problema generale e molto comune. Non possiamo riscrivere tutto il software esistente in maniera "secure by design", magari con un linguaggio di programmazione diverso. La realtà è costituita da miliardi di righe di codice con cui dobbiamo convivere, e per le quali trovare soluzioni "a buon mercato" per renderli più robusti è una strada percorribile e, anzi, abbastanza richiesta.

Da premettere che per me è un "non problema", spostare una delle tante possibili soluzioni lato hardware non mi ispira tantissimo.. abbiamo già architetture abbastanza complesse. Secondo me ultimamente nel mondo dell'informatica si sta perdendo quel concetto di semplicità che spesso è la soluzione migliore per il controllo della complessità di oggi.

Sei un fautore della filosofia RISC. Però anche i RISC moderni hanno ormai centinaia di istruzioni, anche molto specializzate. E questo perché accelerare determinati ambiti / tipi di algoritmi è divenuto una necessità.

(Con questo non voglio sminuire ciò che stai facendo, che sono sicuro sia un ottimo lavoro)

No, assolutamente. Mi spiace soltanto che non possa mostrarti il draft per chiederti un parere. Una cosa che ho imparato dove lavoro è che il peer review è fondamentale, e che le critiche sono importanti sia per un reality check (per non galoppare troppo con la fantasia) sia per riuscire a rendermi conto dei limiti o proprio del valore dell'idea.

P.S. ho letto dell'MPX, non risolve però i problemi dei dangling pointer

No, infatti, e non l'ho mai detto. Il suo ambito è il bound-checking e il tracciamento dell'uso dei puntatori / buffer.

e comunque ci sono delle problematiche che il runtime check non ha (i falsi positivi)

Non è una tecnologia perfetta, e anche la mia non garantisce una soluzione perfetta della problematica in oggetto (idem per i dangling pointer: la mia tecnologia è utile anche in quest'ambito, ma non risolve definitivamente il problema). Si tratta di soluzioni che limitano molto i danni del codice; un buon compromesso, insomma.

[cdimauro]

• 

Sorry per il ritardo ma non ho avuto respiro

Va benissimo (per me è uguale, e da un po' sto rosicchiando ore alle notte pur di riuscire a fare qualcosa), anzi grazie per la risposta.

Puoi fornire un'implementazione che sia più robusta e altrettanto efficiente?

Mi sono preso un po' di tempo (in quel poco che ho) per guardare il .h e un po' il .c, in particolare il commento di documentazione.

Mi permetto una critica perché sulle hash table ho un'esperienza di quasi un decennio. Il fatto che quel codice usi open address al posto del chaining ed una tabella eccessivamente piccola è già una scelta discutibile in un linguaggio che fa largo uso di dict ed è facile che degradi presto a linear list (ovvio che poi richiede il resizing della tabella). Se sono tanto preoccupati per le performance di mallocing, basta utilizzare una migliore allocation strategy oppure ci sono altri metodi di open addressing che non richiedono il resize della tabella. Nell'open address non ha senso partire con una tabella piccola e poi allargarla, ed è nato proprio per evitare l'uso di heap (e per un numero limitato di entry).

Quindi quale "efficienza"? L'unica cosa che vedo è solo una riduzione della memoria utilizzata, ma non della computazione generale.

Serve un po' di tutto, perché i casi di utilizzo di un dizionario sono diversi. Ma ne parlo meglio dopo.

E poi non è bello sapere queste cose per un programmatore Python :-)

ROFL Non pensavo, onestamente. Quindi sarà una sofferenza lavorare ogni giorno in PHP. :-/

ora che lo so userei in modo diverso le dict, in genere mi piace pensare che ci siano casi ottimizzati in generale, non nel particolare (e mi pare di vedere che ce ne siano tanti), per esempio vedo che hanno ottimizzato in un certo senso il caso di dict piccole per le kwargs, e questo è buono perché è molto importante

Fa parte di uno dei casi di utilizzo di un dizionario in Python. Ne posto un breve elenco, che farà meglio capire il perché di quelle scelte che sono frutto di un compromesso.

I dizionari sono usati per memorizzare:
- le variabili d'istanza di un oggetto;
- le variabili globali di un modulo;
- le keyword di una funzione che consente il passaggio di un numero arbitrario di parametri passati per nome e valore;
- dati (le tradizionali "mappe").

Usi comuni sono:
- il lookup per controllare se una chiave (o variabile per i primi due casi; lo sottolineo perché è importante) esiste;
- il recupero del valore;
- l'iterazione di tutte le chiavi;
- l'hashing (calcolare un valore che "rappresenti" il dizionario e ciò che conserva).

Com'è possibile vedere, i casi sono tanti e coprono utilizzi anche molto diversi. L'attuale soluzione rappresenta, dunque, un buon compromesso fra velocità (in particolare per il lookup, che è fondamentale per i primi due casi, altrimenti ammazzerebbe le prestazioni della virtual machine) e spazio occupato (usando un dizionario per tutti i casi elencati, è facile che l'utilizzo della memoria esploda. Infatti per i casi più comuni / utili / necessari, che sono i primi due, si alloca immediatamente un piccolo numero di entry).

Non è possibile scegliere implementazioni diverse a seconda del caso d'uso, perché i dizionari vengono utilizzati in tutti questi ambiti e sono intercambiabili (ad esempio posso rimpiazzare le variabili d'istanza di un oggetto con un altro dizionario).

Internamente si potrebbe anche fare, ma a prezzo di complicare notevolmente l'implementazione, e probabilmente finendo per penalizzare i casi più importanti.

Prova a generare in maniera efficiente una pagina web. Se non ricorri a un oggetto StringBuilder / StringIO / buffer che si allunga a dismisura, i tempi di generazione della pagina saranno estremamente elevati.

Come lo risolvi diversamente, e in maniera più "sicura", questo problema?

Ma in quel modo non ho a che fare con oggetti che non si allungano a dismisura, anzi.. lavorare con chunk di dati è molto meglio, non deallochi/riallochi l'intero dato (causando dangling pointer) ma aggiungi solo ciò che ti serve.

Aggiungi -> prima o poi lo spazio finisce e devi effettuare il resize (quindi, di nuovo, allocare e deallocare).

Utilizzare strutture dinamiche, come liste concatenate (FIFO), richiede più memoria ed è decisamente più lento rispetto a un array con accesso diretto alle sue entry.

L'array allocato dinamicamente è una pessima idea in generale, pensa che molti per risolvere il problema dei dangling pointer utilizzano un puntatore a puntatore (quindi si avrà sempre un riferimento al nuovo array allocato), ma si ha due livello di indirizzamento che rallenta di parecchio l'accesso (questo era il metodo utilizzato dalle glib, non so se le cose siano cambiate).

Chiaro. E' una soluzione che non userei.

Però immagina il tipo PyList, un altro di quelli che viene spesso utilizzato (oppure StringIO, che viene molto usato per generare pagine web o, in generale, buffer di dati che vengono costruiti): cosa utilizzeresti per implementarlo in maniera efficiente a run-time?

A proposito di Glib, implementa un "cesso" di array dinamico (che cresce ad ogni elemento aggiunto), ad ogni g_array_append_val() veniva fatto un malloc(), copia e free() con performance a dir poco VOMITEVOLI! Se si voleva evitare la riallocazione frequente bisognava crearlo con g_array_sized_new() (anziché g_array_new()) per preallocare una buona porzione dati, ma ciò col tempo non bastava (diamine!) che ricominciava col suo diabolico malloc(), copia e free(). Non capisco come mi piaceva quella cagata pazzesca di glib e gtk+, errori di gioventù (avevo 17 anni o su di lì). Spero che oggi sia un tantino ottimizzato, ma non ho interesse a guardarne il codice o la guida

Ho visto soltanto una volta in che modo gestiscono gli oggetti, e... m'è bastato.

Purtroppo è un problema generale e molto comune. Non possiamo riscrivere tutto il software esistente in maniera "secure by design", magari con un linguaggio di programmazione diverso. La realtà è costituita da miliardi di righe di codice con cui dobbiamo convivere, e per le quali trovare soluzioni "a buon mercato" per renderli più robusti è una strada percorribile e, anzi, abbastanza richiesta.

Purtroppo gran parte del codice che c'è (a mio parere) è codice merda, che è meglio riscrivere.

Riscrivere ha un costo, anche molto elevato. Non si può riscrivere tutto, lo sai. Sarebbe bello, ma... è impossibile.

Io sono molto a favore dei runtime check (soprattutto se non sono eccessivamente invasivi ma economici), ci si lamenta tanto di come questi runtime check rallentino il software che poi in realtà i veri bottleneck sono altrove.

Ci sono studi che dimostrano che il bound-checking a runtime è molto costoso. Per questo si cercano soluzioni, sia software (usando l'MMU, ad esempio, e disponendo i dati allocati in un certo modo per generare appositi fault) sia hardware (MPX, o l'accelerazione hardware proposta per AddressSanitizer; ma ce ne sono altre).

Ci sono una miriade di problemi a cui deve badare il programmatore, se un gruppo di questi problemi si può evitare selezionando solo certe tecniche, abilitando certe feature ed evitandone altre, posso solo reputarlo "good engineering". Infatti apprezzo molto quei progetti che hanno delle linee guida, in particolare definiscono un subset degli strumenti a disposizione e soprattutto ne danno una motivazione, uno può non essere d'accordo.. ma che ci sia è una cosa da apprezzare

OK, ma... non si può fare con tutto il codice esistente. Ormai esiste e bisogna conviverci. Col tempo il codice viene riscritto, ma è sempre una goccia d'acqua in un oceano, purtroppo.

[cdimauro]

• 

cmq io mi sa che come soluzione bovina hw punto di prepotenza alle classiche (per i MIPS) TLB entries
in salsa bovina: virtual memory for sandboxing everything

Che non risolve o allieva il problema dei buffer overflow, purtroppo.

semplicemente perche' so come funzionano, e + o - posso pensare a come implementarlo.
per chiudere il giro, e' la stessa conclusione a cui sono giunti in OpenRISC

Quindi OpenRISC è simile ai MIPS per quanto riguarda la gestione delle TLB?

nella versione HP della CPU emulator per motorola 332 EVS
c'era una opzione che permetteva di tracciare TUTTI i puntatori
giusto per vedere se si sfora dal range

quel debugger HP lo fa in hw, ci sono dei comparatori di memoria
per armare i comparatori gli si passa la base del puntatore, ed il size
ci sono trigger che si armano solo quando il PC raggiunge istruzioni
che fanno uso di una EA in cui e' coinvolto un puntatore da controllare

quindi nella parte sw vengono tracciati i punti del codice assembly
dove si fa riferimento al puntatore che si desidera monitorare

tutto viene etichettato in modo incrementale
e gestito in hw con un numero limitato di possibili controlli ( mi pare siano 8 )

dopo di che, in esecuzione, ogni volta che viene incontrata l'istruzione incriminata
scatta il via libera per il comparatore hw, e si controlla l'EA finale
e se sfora si alza una exception
facendo sapere all'utente chi/dove/perche' ha sforato

molto primitivo ma apprezzato
costava un bel po' negli anni '90

Interessante soluzione. Il problema è che è troppo limitata, con soli 8 comparatori.

MPX ha 4 bound register, però ha pure la possibilità di gestire qualunque puntatore perché sfrutta una cosiddetta "Bound Table", che è simile a una Page Table, per mappare tutti i bound da tracciare; soluzione che occupa memoria e risulta un po' costosa.

La mia soluzione, invece, non ha nessun comparatore dedicato e nessun bound register. Ma non posso aggiungere altro, al momento.

[cdimauro]

• 

Sì, ma abbiamo sempre problematiche simili, te l'assicuro.

Anche per questo MPX ha soltanto 4 bound register, anche se poi c'è la Bound Table dalla quale scaricare all'occorrenza.

Il problema di queste soluzioni è che richiedono l'uso del compilatore, per generare le apposite istruzioni per gestire il tutto. Con tutti i limiti del caso.

La mia soluzione, invece, funziona anche con applicazioni già esistenti, ma sotto certe condizioni.

Comunque MPX, come pure il classico bound checking a runtime, comportano un calo delle prestazioni, a causa delle istruzioni aggiuntive da eseguire, e al fatto che il compilatore non può emettere codice altamente ottimizzato (perché deve memorizzare l'indice e/o il puntatore in un registro, per poi fare il controllo).

[cdimauro]

• 

gdb funziona circa in quel modo, cerca di seguire un po' il codice
ma ha tipicamente senso quando il codice segmenta, e non prima
ovvero si cerca grossolanamente il punto dove segmenta
e poi lo si analizza nel dettaglio, seguendo istruzione per istruzione
con strumenti che analizzano lo spazio dei puntatori

Però se non conservi informazioni sul flusso eseguito, non te ne fai nulla: puoi andare indietro soltanto fino a un certo punto, facendo poca strada.

[cdimauro]

• 

Capito. Allora è qualcosa di diverso dall'operato di MPX e del classico bound checking eseguito a runtime.

Comunque quelle di cui hai parlato sono soluzioni complesse, e credo anche molto più onerose.

[cdimauro]

• 

Allo stato attuale, appunto.

[cdimauro]

• 

Purtroppo è molto diffuso, e... si usa quello. Anche Intel ha puntato molto su GDB.

Adesso c'è pure LLDB. Se è fatto bene, magari riuscirà a soppiantarlo.

[cdimauro]

• 

Sì, immaginavo che esistessero soluzioni proprietarie / commerciali. Ma limitatamente a roba open source / gratuita, non credo ci sia molto in giro.