Geekly articles weekly

Kelengkapan tak terduga Turing di mana-mana

Katalog konstruksi perangkat lunak, bahasa, dan API yang tiba-tiba selesai Turing; implikasi ini untuk keamanan dan keandalan. Aplikasi: berapa banyak komputer di komputer Anda?

Setiap program C atau Fortran yang cukup kompleks berisi implementasi setengah dari bahasa Common Lisp yang baru ditulis, tidak ditentukan, bermasalah, dan lambat . - Kesepuluh Greenspan Rule

Turing completeness (TC) adalah properti sistem untuk mengimplementasikan fungsi yang dapat dihitung dengan representasi input dan output yang sederhana.

Kelengkapan Turing adalah konsep dasar dalam ilmu komputer. Ini membantu untuk menjawab banyak pertanyaan kunci, misalnya, mengapa tidak mungkin membuat program antivirus yang sempurna. Tetapi pada saat yang sama, itu adalah kejadian yang sangat umum . Tampaknya sulit bagi sistem komputer untuk mencapai universalitas sedemikian rupa sehingga dapat menjalankan program apa pun, tetapi yang terjadi adalah sebaliknya: sulit untuk menulis sistem yang bermanfaat yang tidak langsung berubah menjadi Turing lengkap. Ternyata bahkan sedikit kontrol atas data input dan mengubahnya menjadi hasil, sebagai suatu peraturan, memungkinkan Anda untuk membuat sistem turing-complete. Ini bisa lucu, berguna (walaupun biasanya tidak ), berbahaya atau sangat tidak aman dan hadiah nyata bagi seorang peretas (lihat "keamanan teori-bahasa" , yang mempelajari metode peretasan "mesin aneh" 1 ) Contoh luar biasa dari perilaku ini mengingatkan kita bahwa kelengkapan Turing bersembunyi di mana-mana, dan sangat sulit untuk melindungi sistem.

Bahasa pemrograman yang terlalu kuat juga dapat memicu serangan DoS yang tidak menyenangkan. Fazzer afl menemukan roff semacam itu di OpenBSD sehingga ia mampu menghasilkan loop tak terbatas , menyalahgunakan beberapa aturan substitusi string.

Mungkin, contoh-contoh tak terduga dari sistem lengkap Turing ini lebih baik dianggap sebagai bagian dari bahasa pemrograman esoterik yang "ditemukan" atau "ditemukan". Jadi FRACTRAN luar biasa minimalis tidak dianggap 2 serta bahasa Malbolge yang dikaburkan secara khusus (di mana penulisan program yang sepele akan memakan waktu bertahun-tahun), karena ini dirancang khusus YaP esoterik. Juga, game "Life" tidak termasuk dalam subset kami, karena pertanyaan tentang kelengkapan Turing muncul segera setelah dirilis, dan pengakuan Turing yang lengkap tidak datang sebagai kejutan. Dan mengingat kompleksitas jaringan dengan perutean dan pengalihan paket, tidak mengherankan bahwa Anda dapat membangun skema seluler atau skema logika program pada jaringan ini, dan merencanakan / memvalidasi tiket tidak hanya tugas yang sulit-NP dan bahkan EXPSPACE-sulit, tetapi sama sekali tidak dapat diselesaikan (karena aturan maskapai yang kompleks).

Banyak konfigurasi, bahasa khusus, alat, atau permainan yang rumit, ternyata, melanggar aturan kekuasaan paling rendah dan “secara tidak sengaja menjadi lengkap Turing” , seperti MediaWiki , sed template atau perintah regexp / find-replace berulang di editor. Secara umum, segala bentuk penggantian garis atau templating, atau kompilasi on the fly dengan probabilitas tinggi adalah sistem Turing-complete sendiri atau ketika diulang, karena mereka sering mendukung kalkulus lambda atau menulis ulang istilah bahasa atau label, misalnya, bahasa esoterik atau kamu.

XSLT , Infinite Minesweeper , Dwarf Fortress 3 , Starcraft, Minecraft , Ant , Transport Tycoon , C ++ templates dan generalisasi Java , perhitungan DNA dan sebagainya - semua ini adalah sistem Turing-complete, dan ini juga tidak mengejutkan. Banyak game mendukung skrip untuk menyederhanakan pengembangan dan mod khusus. Karenanya, untuk membuat game Turing-complete menjadi dasar: cukup nyalakan sintaks untuk memanggil bahasa yang lebih terkenal seperti Perl.

Kelengkapan Turing mungkin hanya sedikit diketahui bagian dari format standar. Mungkin, di zaman kita, banyak yang tidak tahu bahwa TrueType dan banyak font adalah program PostScript pada mesin yang ditumpuk, mirip dengan ELF metadata dan informasi debug DWARF . Atau bahwa beberapa format musik melampaui MIDI , mendukung skrip dan membutuhkan interpretasi. Jika Anda tahu tentang kelengkapan font Turing, maka kelengkapan dokumen Turing dari TeX tidak mengejutkan, yang secara alami menyebabkan banyak kerentanan keamanan yang serius dan menarik dalam font dan media, seperti eksploitasi BLEND atau Linux SNES dan NES . Dalam format lain seperti PDF, hanya ada sejumlah besar kerentanan 4 . Sekali lagi, prestasi luar biasa seperti membuat mesin Turing kecil dari blok Lego atau domino 5 tidak dipertimbangkan, karena kita telah lama mengetahui bagaimana komputer mekanik bekerja.

Di sisi lain, garis penelitian keamanan komputer yang disebut mesin aneh sering mengungkapkan sistem turing-complete yang benar-benar menakjubkan. Selain itu, mereka menyebabkan kejutan pada tingkat yang berbeda pada orang yang berbeda: satu tampaknya tidak biasa yang tidak mengejutkan orang lain.


Mungkin sistem berikut ini secara tidak sengaja akan menyelesaikan lengkap:

  • CSS tanpa klik
  • SVG: PostScript adalah TC berdasarkan desain, tetapi bagaimana dengan format grafik vektor SVG yang lebih modern, yang ditulis dalam XML, yaitu, dalam bahasa dokumen yang (biasanya) tidak Turing-complete? Tampaknya dalam kombinasi dengan XSLT mungkin masih demikian, tetapi saya belum menemukan bukti atau demonstrasi ini dalam konteks browser web yang biasa. Standar SVG sangat bagus dan kadang-kadang menakutkan: versi SVG 1.2 yang gagal mencoba menambah kemampuan untuk membuka soket jaringan dalam gambar SVG.
  • Unicode : Nicholas Seriot menyarankan bahwa algoritma Unicode dua arah (dirancang untuk menampilkan skrip kanan-ke-kiri, seperti bahasa Arab atau Ibrani) dapat cukup kompleks untuk mendukung sistem tag melalui aturan case- sensitive (mis., Turki)

Lihat juga



Referensi



Aplikasi


Berapa banyak komputer di komputer Anda?


Beberapa terjebak dalam perselisihan tentang mobil aneh atau tentang seberapa "besar" agen AI akan menjadi: satu seperti itu, dua, sepuluh, atau jutaan akan dibuat. Itu tidak masalah, karena ini hanya masalah organisasi. Sebenarnya, input dan output dari sistem itu penting: seberapa efisien sistem secara keseluruhan dan sumber daya apa yang dikonsumsinya? Tidak ada yang peduli jika Google berjalan pada 50 superkomputer, 50.000 mainframe, 5 juta server, 50 juta prosesor tertanam / seluler, atau kombinasi dari semua hal di atas . Tidak masalah bahwa Google menggunakan beragam chip: mulai dari "prosesor tensor" buatan sendiri hingga prosesor silikon unik (Intel menjualnya pada chip untuk prosesor Xeon untuk sejumlah pelanggan utama), FPGA, GPU, CPU, hingga peralatan yang lebih eksotis seperti komputer kuantum D-Wave . Yang penting adalah tetap kompetitif dan dapat memberikan layanan dengan biaya moderat. Pada akhirnya, hari ini superkomputer biasanya terlihat seperti sejumlah besar server rak dengan sejumlah besar GPU dan koneksi InfiniBand berkecepatan tinggi. Artinya, superkomputer tidak jauh berbeda dari pusat data, seperti yang mungkin Anda pikirkan. Peralatan apa pun yang terdaftar dapat mendukung banyak mesin aneh, tergantung pada dinamika internal dan konektivitasnya.

Demikian pula, sistem AI apa pun dapat diimplementasikan dalam bentuk satu jaringan saraf raksasa atau banyak jaringan saraf terpisah yang beroperasi secara tidak serempak, atau sebagai perangkat layanan mikro yang heterogen, atau sebagai "masyarakat pikiran" dan seterusnya. Semua ini tidak terlalu penting. Dari sudut pandang kompleksitas atau risiko, tidak begitu penting bagaimana sistem itu diatur saat bekerja. Sistem ini dapat dilihat pada banyak tingkatan, yang masing-masing sama-sama tidak valid dalam dirinya sendiri, tetapi berguna untuk tujuan yang berbeda dalam sistem umum.

Berikut adalah contoh pertanyaan yang tidak jelas: berapa banyak komputer yang Anda miliki di saku dan di meja Anda sekarang? Berapa banyak komputer di "komputer" Anda? Pikirkan hanya satu? Mari kita lihat lebih dekat.

Ini bukan hanya tentang CPU: saat ini, transistor dan core prosesor sangat murah sehingga sekarang sering masuk akal untuk mengalokasikan core terpisah untuk tugas-tugas real-time, untuk meningkatkan kinerja, untuk keamanan, untuk menghindari memuat OS utama, untuk kompatibilitas dengan arsitektur lama atau paket perangkat lunak yang ada. Hanya karena DSP atau kernel lebih cepat diprogram daripada membuat ASIC khusus, atau karena itu adalah solusi yang paling sederhana. Selain itu, banyak komponen ini dapat digunakan sebagai elemen komputasi, bahkan jika mereka tidak dimaksudkan atau bahkan menyembunyikan fungsi ini.

Jadi:

  • Dalam prosesor Intel konvensional, miliaran transistor melakukan banyak tugas:

    • Masing-masing dari 2-8 core prosesor utama dapat bekerja secara independen, menyalakan dan mematikan seperlunya, ia memiliki cache sendiri (lebih besar dari RAM di sebagian besar komputer hingga saat ini), dan harus dianggap sebagai komputer independen.
    • CPU secara keseluruhan diprogram ulang melalui mikrokode, misalnya, untuk menghilangkan kesalahan desain chip, dan memamerkan objek yang semakin buram, seperti Intel Management Engine (dengan JVM untuk pemrograman ; Rouen, 2014 dan SGX ) atau AMD Platform Security Processor (PSP), atau Android TEE Modul perangkat keras ini, sebagai suatu peraturan, adalah komputer lengkap dengan haknya sendiri, bekerja secara independen dari host, dan dapat mengganggu operasinya.
    • Setiap FPU dapat menjadi sistem Turing-lengkap melalui pengkodean dalam operasi floating point dalam semangat FRACTRAN.
  • MMU dapat diprogram menjadi mesin kesalahan halaman yang aneh, seperti yang disebutkan di atas.
  • Blok DSP , chip khusus. Mungkin, ASIC untuk format video seperti h.264 tidak akan menjadi sistem turing-lengkap (meskipun didukung oleh delta kompleks dan metode kompresi yang dapat memungkinkan sesuatu seperti ubin Van). Tetapi Apple A9 mobile SoC jauh melampaui prosesor ARM dual-core yang biasa dengan GPU terintegrasi. Seperti Intel atau chip desktop AMD, ini mencakup lingkungan yang aman yang disebut Enklave Aman (inti prosesor yang dialokasikan secara fisik), tetapi juga berisi coprocessor untuk gambar, coprocessor untuk pengenalan suara (sebagian untuk mendukung Siri), dan, tampaknya, beberapa core lainnya. ASIC ini kadang-kadang ada untuk tugas-tugas AI dan, tampaknya, berspesialisasi dalam multiplikasi matriks untuk jaringan saraf, dan karena jaringan saraf berulang Turing lengkap, maka ... Anda mengerti. Motorola, Qualcomm dan perusahaan lain juga bergegas memperluas SoC mereka.
  • Motherboard BIOS dan / atau chip kontrol akses jaringan.

    • Mark Ermolov mencatat:

      “Sungguh menakjubkan berapa banyak inti prosesor heterogen yang diintegrasikan ke dalam Intel Silvermont Moorefield SoC (ANN): x86, ARC, LMT, 8051, Audio DSP, masing-masing dengan firmware sendiri dan dukungan untuk antarmuka JTAG

    Chip kontrol atau debugging ini dapat "secara tidak sengaja" tetap diaktifkan pada perangkat setelah penjualan, seperti ARM bawaan pada CPU Via C3 .
  • GPU memiliki beberapa ratus atau ribuan inti sederhana, yang masing-masing bekerja sangat baik dengan jaringan saraf atau melakukan perhitungan tujuan umum (walaupun lebih lambat dari prosesor).
  • Kaset, hard drive, flash drive, dan pengontrol SSD biasanya berjalan pada prosesor ARM untuk menjalankan utilitas bawaan untuk tugas-tugas seperti menyembunyikan sektor buruk dari sistem operasi. Mereka bisa diretas. Tetapi prosesor ARM digunakan di sebagian besar aplikasi yang disematkan, jadi ARM senang menyombongkan diri bahwa “smartphone modern mengandung 8 hingga 14 prosesor ARM, salah satunya adalah prosesor aplikasi (menjalankan Android atau iOS), dan yang lainnya adalah prosesor untuk tumpukan pita frekuensi (tumpukan pita dasar) . "
  • chip jaringan melakukan pemrosesan independen untuk DMA (berkat fungsi independen seperti Wake-on-LAN untuk kerja netboot ).
  • smartphone: selain semua blok yang disebutkan, ada juga prosesor baseband independen yang berjalan di bawah OS real-time sendiri untuk memproses komunikasi dengan menara seluler / GPS / dll. Atau bahkan lebih dari satu jika Anda menggunakan virtualisasi seperti L4 . Backdoors telah terdeteksi di prosesor baseband, selain kerentanan lainnya.
  • Kartu SIM untuk ponsel cerdas jauh lebih dari sekadar kartu memori dengan rekaman data pelanggan Anda. Ini adalah kartu pintar yang dapat menjalankan aplikasi Java Card secara mandiri (mungkin juga chip NFC). Ini seperti JVM di IME. Secara alami, kartu SIM dapat diretas dan digunakan untuk pengawasan, dll.
  • Perangkat yang terhubung melalui USB atau ke motherboard dapat dilengkapi dengan prosesor mereka sendiri. Sebagai contoh, adapter WiFi, keyboard, mouse, dll. Secara teoritis, kebanyakan dari mereka terisolasi dari gangguan langsung dengan host melalui DMA dan IOMMU, tetapi iblis ada dalam rincian ...
  • chip aneh acak seperti MacBook Touch yang menjalankan WatchOS .
  • ...

Jadi di smartphone atau komputer desktop biasa akan ada lima belas hingga beberapa ribu komputer dalam arti perangkat turing-lengkap. Masing-masing dapat diprogram, ia memiliki kekuatan yang cukup untuk menjalankan banyak program dan dapat digunakan oleh penyerang untuk memantau, mengeksfiltrasi, atau menyerang seluruh sistem.

Tidak ada yang tidak biasa dalam konteks historis, karena bahkan mainframe pertama biasanya termasuk beberapa komputer, di mana komputer utama melakukan pemrosesan batch, dan komputer bantu menyediakan operasi I / O kecepatan tinggi, yang jika tidak akan mengganggu mesin utama dengan interupsi mereka.

Dalam praktiknya, di samping komunitas keamanan informasi (karena semua komputer ini tidak aman dan, oleh karena itu, berguna bagi NSA dan penulis virus), semua pengguna lain tidak peduli bahwa di balik tenda komputer kita terdapat sistem rumit yang gila-gilaan, yang lebih akurat dianggap sebagai serangkaian perubahan ratusan. komputer saling terhubung secara memalukan (tidak jelas, "jaringan adalah komputer" atau "komputer adalah jaringan" ...?). Pengguna memahami dan menggunakan ini sebagai satu komputer.


1. Bidang penelitian aktif adalah penciptaan bahasa dan sistem yang dirancang dengan cermat dan dijamin tidak akan lengkap-turing (misalnya, pemrograman yang benar-benar fungsional ). Mengapa berupaya keras menciptakan bahasa yang tidak bisa ditulis oleh banyak program? Faktanya adalah bahwa kelengkapan Turing terkait erat dengan teorema ketidaklengkapan Gödel dan teorema Rice.. Karena itu, jika TC diizinkan, maka kami kehilangan semua kemungkinan properti yang dapat dibuktikan. Sebaliknya, berbagai hal berguna dengan mudah dibuktikan dalam bahasa Turing-tidak lengkap: misalnya, bahwa suatu program lengkap, aman atau tidak, bahwa mudah untuk dikonversi ke teorema logis, bahwa ia mengkonsumsi sumber daya dalam jumlah terbatas, bahwa implementasi protokol adalah benar atau setara dengan implementasi lain. Sangat mudah untuk membuktikan bahwa tidak ada efek samping dan bahwa program dapat dikonversi ke opsi yang setara secara logis, tetapi lebih cepat (ini sangat penting untuk bahasa deklaratif seperti SQL, di mana kemampuan pengoptimal untuk mengkonversi kueri adalah kunci untuk kinerja yang dapat diterima. Meskipun, tentu saja, hal-hal menakjubkan dapat dilakukan dengan SQL, sepertigradient descent untuk model pembelajaran mesin , dan beberapa ekstensi SQL membuatnya turing lengkap , memungkinkan Anda untuk menyandikan sistem loop , atau modelDSL , atau panggilan PL / SQL , dll.

Berikut ini beberapa literatur tentang mobil-mobil aneh:


↑

2. Meskipun jaringan saraf linier mengeksploitasi mode floating point dengan pembulatan ke nol untuk mengkodekan perilaku berpotensi-lengkap Turing (untuk RNN), itu tidak terlihat dalam operasi normal, yang juga merupakan perilaku Turing-lengkap acak dan contoh yang baik dari bahasa yang aman. ↑

3. Dwarf Fortress menyediakan jarum jam, jadi kelengkapan Turing tidak mengejutkan. Tetapi air juga diimplementasikan sebagai otomat seluler sederhana, sehingga ada lebih banyak cara untuk mendapatkan kelengkapan turing! Sekarang, game wiki menyebutkan empat cara potensial untuk membuat gerbang logika: cairan, mekanisme jarum jam, gerobak tambang dan gerbang logika makhluk / hewan dengan pintu dan sensor tekanan. ↑

4. Spesifikasi PDF lengkap sangat membengkak. Misalnya, dalam penampil PDF sederhana yang cukup mendukung spesifikasi PDF, seperti browser Google Chrome, Anda dapat memainkan Breakout (karena PDF menyertakan subset JavaScript yang aneh). Penampil Adobe PDF resmi mendukung fungsionalitas hingga CAD tiga dimensi. ↑

5. Lihat gerbang logika domino pada Think Math dan demo dari 4-bit domino knuckle adder . ↑

Source: https://habr.com/ru/post/id429602/

More articles:


All Articles