Convalida la correttezza tra le risposte non attendibili

3

Sto giocando a un progetto di calcolo distribuito. L'applicazione client richiede un problema da risolvere. Il server restituisce una descrizione del problema da un "pool di problemi". Al termine del client, restituisce la soluzione.

Non posso fidarmi dei miei utenti e quindi non posso fidarmi delle loro soluzioni. Ho bisogno in qualche modo di convalidare le loro soluzioni corrette (per alcune definizioni di "corretto"). Chiunque potrebbe inviare una soluzione sbagliata al problema che gli è stato assegnato. Voglio convalidare due cose:

  1. Nessuno può pubblicare una soluzione per un problema che non ho dato loro. Penso che questo sia facile: do loro un HMAC dell'ID problema più il mio segreto e controlla che inviino gli stessi token con la soluzione.
  2. Voglio verificare che la soluzione dell'utente sia corretta. Voglio fare questo controllo senza risolvere il problema da solo. E ancora più importante, non voglio che la soluzione sia specifica del problema, quindi non posso usare alcune proprietà dei problemi, che potrebbero funzionare per problemi NP- (Complete / Hard), per esempio.

Supponiamo, per il gusto della discussione, di calcolare le cifre di PI. Quindi, come posso essere sicuro che la risposta di alcuni utenti per l'ennesima cifra di PI sia corretta? Devo dare lo stesso problema a più utenti e cross validate? In che modo questo problema viene gestito in progetti come SETI @ home e altri?

    
posta Alejandro Piad 13.11.2013 - 22:03
fonte

1 risposta

2

Distributed.net ha risolto questo problema assegnando lo stesso spazio di ricerca a più utenti e li ha convalidati in questo modo. (Probabilmente lo stanno ancora facendo.)

A seconda del costo del calcolo e dei livelli di partecipazione, potresti voler ricontrollare solo una piccola parte dei pacchetti. Il confronto del 5% dovrebbe darti una possibilità statisticamente valida di catturare un imbroglione. Assicurati di distribuire in modo casuale i blocchi di sfida duplicati in giro, in modo da non avere solo l'utente A che convalida i pacchetti di B dell'utente. Non identificare i blocchi di test in alcun modo, ad esempio l'invio di dimensioni o intervalli diversi, oppure un imbroglione potrebbe manometterli. E infine, sappi che un risultato positivo non indica un imbroglione maligno. Potrebbe essere un problema hardware o software. Devi vedere un modello di abuso prima di staccare qualcuno.

EDIT:

Ecco un collegamento al documento Autenticazione codice operativo di distributed.net . Descrive i meccanismi di sicurezza con cui gestiscono la convalida del lavoro di lavoro distribuito a clienti non regolabili. Di particolare interesse sono alcuni degli altri problemi di sicurezza che hanno identificato, come "rubare la soluzione", in cui un malfattore distribuisce un client modificato a qualcun altro. Il cliente modificato sopprime il segnale "risultati vincenti" e invia invece i risultati all'attaccante, che reclama e riscuote ingiustamente il premio per la scoperta.

    
risposta data 14.11.2013 - 00:46
fonte

Leggi altre domande sui tag