.svg)
キルチェーンとIoTと量子組み合わせ最適化: バズワードサラダ
ソースにより数字に差はあるものの、サイバーセキュリティの市場規模は現在（2023年8月時点）年間数千億米ドルと推定されています。IoTの市場規模を見積もるのは、サイバーセキュリティよりも定義が曖昧なため困難です。例えば、ウェブに接続されたトースターはIoTデバイスに入るのでしょうか？そうかもしれませんが、卵パックに貼られたマイクロチップ内蔵のRF（無線周波数）識別タグはどうでしょう？それもIoT関連と言えるでしょう。偶然にも、どちらの例もサイバー攻撃の標的になり得ます。そのうちインターネットに接続された邪悪なサイバー攻撃能力を持つキツネが、インターネットに接続された美味しいお菓子を標的にするかは不明です。
正確な市場規模がどうであれ、どちらの市場も巨大で魅力的であることは間違いありません。量子計算市場は、非常に早熟ではありますが、まだはるかに小規模です。ここでは甘い推定でその市場規模をサイバーセキュリティ市場の約1％（またはそれ以下）、年間約10億ドルと見積もってみましょう。 とはいえ、成長予測は驚異的です。
予測される成長の一部は、量子計算機能が他の市場をどのように活性化させるかによってもたらされます。特に本日の記事では、量子アルゴリズムを組合せ最適化に使用することで、古典的なアルゴリズムの市場であるIoTとサイバーセキュリティを、上回る可能性があることを説明します。
1日1回のパッチで攻撃者を防ぐ
サイバーセキュリティとはそもそも何でしょうか？それは、悪意ある行為者が、あなたがアクセスされたくないもの-あなたのデータ、あなたのコンピューター、そしてあなたのトースター-にアクセスできないようにする技術と技巧です。やっかいなのは、最近ではコンピュータ・システムがネットワークから切り離されていることはあまりない点です。すべてがネットワークを介してメッシュ状になっており、基本的には相互接続されたアセットの大規模な集合体なのです。
ネットワーク上の各アセットは、それ自体がソフトウェアであるか、あるいはそれに関連するソフトウェアを持っています。機密性の高いデータベースには、自分だけのものにしたい情報が含まれており、特定のデータベースベンダーと特定のバージョンで動作しています。OSのネットワークレイヤーの設計に見落としがあったために、誰かがその穴を突いて、あなたのコンピュータを無許可のハリーポッターの二次創作小説の配信ノードにしてしまうことが起こりえます。
ほとんどの複雑なシステムと同様、コンピューターシステムも常に、本来の設計者が意図しない利用をうっかり許してしまうことがあります。幸運なことに、コンピュータの場合、既知の穴を塞ぐパッチを配布することができます。ネットワーク上のアセットに正しくパッチを当てることは、健全なサイバーセキュリティネットワークにとって最も重要な要素の一つです。しかし、それは簡単なことではありません。
パッチを使用して既知の問題をすべて密封するには、多くの障壁があります。何よりもまず、追跡して適用する必要がある膨大な数に圧倒されます。以下は、オンラインの脆弱性登録であるCVEで収集された、公表された既知の問題の数です。脅威の増加傾向は明らかであり、その数は数万に及びます。パッチ適用には互換性の問題も考慮する必要があり、システム性能に影響を及ぼす可能性があり、異種ネットワーク間で調整しなければならないことから、これが克服するにあたり困難な課題であることは明らかです。
適切な場所に適切なパッチを当てる
物理学者ユージン・ヴィグナーはかつて、自然科学において数学は「理不尽なほど効果的」だとコメントしました。平たく言えば、「問題を解決したければ数学的モデルを作るのが良い」ということです。だからパッチの問題でもおそらくそれに習うべきでしょう。ここで紹介するモデルは、[https://arxiv.org/abs/2211.13740]で発表されたオリジナルの研究を踏襲したもので、グラフ理論モデルです。まずは定義から始めましょう。
- 私たちは、アセットと脆弱性をリンクさせたグラフを扱います。
- アセットとは、攻撃者にとって価値のあるもの、例えばシステムに保存されているデータなどを指します。アセットの可用性、一貫性、完全性を維持する必要があります。
-脆弱性とは、攻撃者がアセットを悪用するための欠陥を指します。例えば、パッチが正しく適用されていないソフトウェア、脆弱なパスワード、不十分なネットワーク設定などが含まれます。
あるアセットと脆弱性が関連しているということは、そのアセットが脆弱性の影響を受けやすいことを示しています。このコンピューターにはあまりに短いパスワードがある、あのコンピューターは20年前の純正Windows XPが動いている、などの状況です。このようなリンクは、そのコンピューターにアクセスする方法が知られていることを意味します。パスワードが "Password "であることを推測するような方法です（不可解なことに、これは今でも非常に確率の高い推測ですhttps://en.wikipedia.org/wiki/List_of_the_most_common_passwords）。
影響を受けるアセットを持つことの危険性は、そのような「チェーンリンク」が一緒にくっつく可能性があることです。つまり、一見無関係に見える複数の安全でないリンクが組み合わさると、攻撃者はネットワーク内を横方向に移動できるようになります。そして攻撃者は、目的の重要アセットを狙うための完全な攻撃シナリオを確立することができます。下の画像には、この一連の動きが示されています。1998年のスティーブン・セガールの映画のような名前ですが、脆弱性をつなぎ合わせることをキルチェーンと呼びます。
高価なものをどこに置くか
私たちはまだネットワークにパッチを当てたいと願っています。しかし、少し回り道をして、本質的な数学的概念を説明し、それがIoTアプリケーションの安全性を確保するためにどのように使われるかを示唆する必要があります。
IoTのシナリオの一例として、通信するセンサーの大規模な集合が使用されます。ワイヤレスセンサーネットワーク（WSN）は、山火事から森林を守る場合（湿度、温度、気圧などの様々な環境要因に敏感なセンサーを配置する場合）、多くの機械が一体となって動作する産業アプリケーションを監視する場合、輸送ネットワークを調整する場合など、多くの場面で展開されます。以下の[1]の図は、11ノードのWSNを示しています。ノード番号1は、ネットワークを制御し、ネットワークから情報を集中的に収集するため、他のノードとは異なるマークが付けられています。
WSNは、他のコンピュータネットワークと同様、攻撃の標的になり得ます。私がアイスクリーム工場を経営しており、競合他社は私がミントチョコレートチップを作る温度を知りたがっているとしましょう。ここでどうやってネットワークを守ればいいのでしょうか？
ネットワークノードの中には、他のノードよりもインテリジェントなものがあります。例えば、ネットワーク上でやり取りされる情報（ネットワークパケット）の内容を検査し、悪意のあるパケットがあればアラートを出すといったモニタリング機能を持つことができます。この種のアプリケーションはリンクモニタリングシナリオと呼ばれます。
WSNのすべてのノードをモニタリングノードにすることは現実的ではありません。ノードあたりの実際のコストとエネルギー消費の点で、コストが膨れ上がってしまいます。例えば、ノードが広大な森林に広がっていて、バッテリーで動作しているとします。その場合、頻繁にバッテリーを交換する必要が出てくるでしょう。それよりもエネルギーを節約できるノードを配置すれば、生活はずっと楽になります。すべてのノードをスマートにして、電力を消費させ、高価にすることは、良い方法とは考えられません。
ここで、ネットワーク内のどのノードが最も他のノードを「見ている」のかを考えてみましょう。下の図も[1]から引用したもので、赤色で示されたモニタリングノードの一部を示しています。
グラフ理論では、グラフ全体を可能な限り「見る」ことができる（すなわち、接続されている）ノードの選択を、グラフの最大頂点被覆（MVC）と呼びます[https://en.wikipedia.org/wiki/Vertex_cover]。
MVCを求めるのは簡単な計算作業ではありません。技術的にはNP困難に分類される問題です。このような問題には、検証は簡単だが（簡単とは、解が成り立つかどうかを「多項式時間」で比較的速くチェックできることを意味します）、見つけるのが難しい（迅速な、つまり「多項式時間」で見つけることができない）解が存在します。
ここで量子計算の登場です。量子アルゴリズムを使ってMVC問題の近似解を求めることができます！
量子パッチの適用
さて、元の問題であるパッチ管理に戻りましょう。我々のゴールは、コンピュータネットワークにどのパッチを適用すれば最も多くキルチェーンを破壊できるかを特定することです。
数学的グラフは量子アルゴリズムが好むデータ構造です。それらには、グラフを分割するアルゴリズムや、グラフの中を検索するアルゴリズムなどがあります。
我々が苦境を表現するために使っているグラフは、技術的には2部グラフとして知られています。つまり、2つの異なるタイプ（アセットと脆弱性）のノードの集まりで、エッジによって接続されています。エッジは、攻撃者があるアセットから別のアセットへ、そのアセットで利用可能な脆弱性を悪用して移動する能力を表しています。
上で示したキルチェーンを二部グラフで表してみましょう。1,4,8という数字は特定の脆弱性を表し、特に意味はありません。ただ、既知の脆弱性リストの中から特定の脆弱性を選んだと想像してください。
このグラフから脆弱性とアセットを繋ぐエッジをすべて取り除きたいとします。これは、すべてのアセットにすべてのパッチを適用し、すべてを100％セキュアにしたいと言っているようなもので、それは現実的ではありません。そこで、キルチェーンを断ち切るような、脆弱性に優先順位をつける戦略を見つける必要があります。この単純な例では、脆弱性4を排除することでキルチェーンが途切れます。
これを見るための方法を紹介しましょう。この単純な例のためにグラフをさらに修正するのは奇妙に思えるかもしれませんが、後々より複雑なシナリオで役に立つことがわかります。まず双対グラフを定義しましょう。
双対グラフは脆弱性に注目し、それらが「元の」グラフのアセットを介してつながっている場合、それらを直接つなげます。これが今回の例の双対グラフです：
脆弱性4を取り除けばチェーンが断ち切られるという以前からの直感は、今やより明白なものとなり、1から8への移動は不可能となります。
もっと複雑なグラフだったら？
より多くのアセットと脆弱性を持つ、より複雑な例を考えてみましょう。何十万ものノードを持つ実際のネットワークに比べれば、まだおもちゃのモデルに過ぎませんが、すでに視覚的に複雑になっています。
これを双対グラフに変換すると以下のようになります：
ここでは単純化のため、無向グラフを作成しました。これは、方向に関係なく連鎖を断ち切り、最もよくつながっている脆弱性を優先するためです。またその方が作業が楽になり、単純なものから始めて徐々に複雑さを導入していく方が良いことも多いでしょう。多くの物事はそのままでは複雑なのです。
このグラフを見ても、どのノードを削除すれば最もキルチェーンを断ち切れるかは明らかではありません。ではどうすればよいのでしょうか？もちろんMVCを見つけることです！
双対グラフのMVCは、どのパッチを適用すれば最も多くのパッチ未適用のノードを互いに切り離し、脆弱性の連鎖を防ぐことができるかを教えてくれます。つまり、キルチェーンを断ち切ることが可能です。
この場合、青でマークされたノードがMVCソリューションを示しています。最小のコストで最大の防御を得るためには、これらのパッチを適用すべきです。
この解は2部グラフの形に戻すことができ、以前よりもずっと単純な形を示します。重要なのは、ある脆弱性から別の脆弱性へとアセットを経由して移動することは不可能だということです。チェーンは切れているのですから。
MVCと量子：Classiqの解法
これでサイバーセキュリティの問題に取り組む数学的な方法ができました。リンクモニタリングの例でも、キルチェーンの例でも、重要なのはMVCを見つけることです。簡単ですね。
すでに述べたように、問題はMVCを見つけることがNP困難なことです。実際の企業ネットワークには10万以上のホストが存在する可能性があるため、これは一般的に解決困難な問題です。
近似的な最大頂点被覆の探索は、量子コンピュータが取り組む組合せ最適化問題のクラスの主力である量子アルゴリズムを使えば、量子コンピュータ上で指数以下の時間で行うことができます。それがQAOA（量子近似最適化アルゴリズム）です。
MVCは組み合わせ最適化問題の典型的な例です。その難しさは、アイテムの組み合わせの数が非常に多いことに起因します。特定の組み合わせを選択する際には、通常、いくつかの制約を満たす必要があり、選択方法をスマートにするための十分な構造が問題には存在しません。結局、あらゆる可能性をチェックして、うまくいくものを見つける必要が生じます。つまり、解を見つけるには、問題の大きさに比例して指数関数的な時間がかかります。
QAOAを使えば、少なくとも厳密解ではなく近似解を求めることを厭わなければ、それよりも速く、あるいは指数以下の速さで解くことができます。ここではQAOAについて深く説明はしないものの、もし希望される読者が多ければ（ClassiqのSlackサーバーに連絡してください）、将来QAOAについて説明するかも知れません。またオンラインで多くのレビューを読むことができます。例えばこちら[https://arxiv.org/abs/2306.09198]。
QAOAを使った組合せ最適化問題への取り組みは、Classiqプラットフォームが得意とするところです。ここでは3つの簡単なステップを踏む必要があります：
1.Classiqの組合せ最適化機能を使って量子モデルを定義する
2.Classiqエンジンを使ってパラメータ化された量子回路を生成する
3.Classiqプラットフォーム内で回路を実行し、解を表す最適なパラメータを得る
QAOAとグラフを含むClassiqモデルを構築する手法は、標準的なオープンソースのツールと互換性があるため、極めて自然です。Classiq Python SDKを使用する場合、ネットワークグラフはまずnetworkxライブラリで構築されます。 次に最適化問題を定義しますが、ここでは様々な最適化言語が存在します。Pythonエコシステムでこれを行う汎用的で表現力豊かな方法の1つは、PythonのPyOmo言語 [http://www.pyomo.org/]を使うことです。PyOmoは強力でリッチであり、ユーザーは多数の最適化モデルを表現することができます。ユニークなことに、PyOmoはClassiqモデル[https://docs.classiq.io/latest/tutorials/advanced/optimization/]と緊密に統合されているのも特徴です。
次の画像は、Classiqプラットフォームによって合成された回路で、単純な双対ネットワークの近似MVCを見つけています。この回路は実際の量子ハードウェアやClassiqプラットフォームのシミュレータ上でボタンをクリックするだけで簡単に実行できます。
ぜひ、皆様もご自身でお確かめください。platform.classiq.ioへのへの登録は現在完全無料です。Classiqで利用可能なサイバーセキュリティ関連のサンプルモデルが用意されています。量子シミュレータと、複数のハードウェアプラットフォームの両方にアクセスできます。特定のハードウェアターゲット用に回路を書き直す必要はありません。
結論
サイバーセキュリティは、コンピュータネットワークに大混乱を引き起こし、コスト高や危険な混乱を引き起こす可能性のある、無数の隠れた問題を抱えています。これらの課題のいくつかは、数学的に定式化し、計算ツールを用いて取り組むことが可能です。
私たちが日常生活で依存している現代のコンピューターネットワークの規模は計り知れないものがあり、サイバーセキュリティにおける計算問題のいくつかを解決することは、通常の計算リソースでは不可能です。
幸いなことに、量子計算には解決策を見つけることを可能にするツールがありますが、これらの解決策を探索する量子ソフトウェアを生成する方がより現実的かもしれません。
Classiqプラットフォームは、PyOmo言語のような最適化問題で使われる標準的なツールを使って、最先端の量子アルゴリズムを実世界の問題に適用するための最善かつ最も簡単な方法を提供しています。
ソースにより数字に差はあるものの、サイバーセキュリティの市場規模は現在（2023年8月時点）年間数千億米ドルと推定されています。IoTの市場規模を見積もるのは、サイバーセキュリティよりも定義が曖昧なため困難です。例えば、ウェブに接続されたトースターはIoTデバイスに入るのでしょうか？そうかもしれませんが、卵パックに貼られたマイクロチップ内蔵のRF（無線周波数）識別タグはどうでしょう？それもIoT関連と言えるでしょう。偶然にも、どちらの例もサイバー攻撃の標的になり得ます。そのうちインターネットに接続された邪悪なサイバー攻撃能力を持つキツネが、インターネットに接続された美味しいお菓子を標的にするかは不明です。
正確な市場規模がどうであれ、どちらの市場も巨大で魅力的であることは間違いありません。量子計算市場は、非常に早熟ではありますが、まだはるかに小規模です。ここでは甘い推定でその市場規模をサイバーセキュリティ市場の約1％（またはそれ以下）、年間約10億ドルと見積もってみましょう。 とはいえ、成長予測は驚異的です。
予測される成長の一部は、量子計算機能が他の市場をどのように活性化させるかによってもたらされます。特に本日の記事では、量子アルゴリズムを組合せ最適化に使用することで、古典的なアルゴリズムの市場であるIoTとサイバーセキュリティを、上回る可能性があることを説明します。
1日1回のパッチで攻撃者を防ぐ
サイバーセキュリティとはそもそも何でしょうか？それは、悪意ある行為者が、あなたがアクセスされたくないもの-あなたのデータ、あなたのコンピューター、そしてあなたのトースター-にアクセスできないようにする技術と技巧です。やっかいなのは、最近ではコンピュータ・システムがネットワークから切り離されていることはあまりない点です。すべてがネットワークを介してメッシュ状になっており、基本的には相互接続されたアセットの大規模な集合体なのです。
ネットワーク上の各アセットは、それ自体がソフトウェアであるか、あるいはそれに関連するソフトウェアを持っています。機密性の高いデータベースには、自分だけのものにしたい情報が含まれており、特定のデータベースベンダーと特定のバージョンで動作しています。OSのネットワークレイヤーの設計に見落としがあったために、誰かがその穴を突いて、あなたのコンピュータを無許可のハリーポッターの二次創作小説の配信ノードにしてしまうことが起こりえます。
ほとんどの複雑なシステムと同様、コンピューターシステムも常に、本来の設計者が意図しない利用をうっかり許してしまうことがあります。幸運なことに、コンピュータの場合、既知の穴を塞ぐパッチを配布することができます。ネットワーク上のアセットに正しくパッチを当てることは、健全なサイバーセキュリティネットワークにとって最も重要な要素の一つです。しかし、それは簡単なことではありません。
パッチを使用して既知の問題をすべて密封するには、多くの障壁があります。何よりもまず、追跡して適用する必要がある膨大な数に圧倒されます。以下は、オンラインの脆弱性登録であるCVEで収集された、公表された既知の問題の数です。脅威の増加傾向は明らかであり、その数は数万に及びます。パッチ適用には互換性の問題も考慮する必要があり、システム性能に影響を及ぼす可能性があり、異種ネットワーク間で調整しなければならないことから、これが克服するにあたり困難な課題であることは明らかです。
適切な場所に適切なパッチを当てる
物理学者ユージン・ヴィグナーはかつて、自然科学において数学は「理不尽なほど効果的」だとコメントしました。平たく言えば、「問題を解決したければ数学的モデルを作るのが良い」ということです。だからパッチの問題でもおそらくそれに習うべきでしょう。ここで紹介するモデルは、[https://arxiv.org/abs/2211.13740]で発表されたオリジナルの研究を踏襲したもので、グラフ理論モデルです。まずは定義から始めましょう。
- 私たちは、アセットと脆弱性をリンクさせたグラフを扱います。
- アセットとは、攻撃者にとって価値のあるもの、例えばシステムに保存されているデータなどを指します。アセットの可用性、一貫性、完全性を維持する必要があります。
-脆弱性とは、攻撃者がアセットを悪用するための欠陥を指します。例えば、パッチが正しく適用されていないソフトウェア、脆弱なパスワード、不十分なネットワーク設定などが含まれます。
あるアセットと脆弱性が関連しているということは、そのアセットが脆弱性の影響を受けやすいことを示しています。このコンピューターにはあまりに短いパスワードがある、あのコンピューターは20年前の純正Windows XPが動いている、などの状況です。このようなリンクは、そのコンピューターにアクセスする方法が知られていることを意味します。パスワードが "Password "であることを推測するような方法です（不可解なことに、これは今でも非常に確率の高い推測ですhttps://en.wikipedia.org/wiki/List_of_the_most_common_passwords）。
影響を受けるアセットを持つことの危険性は、そのような「チェーンリンク」が一緒にくっつく可能性があることです。つまり、一見無関係に見える複数の安全でないリンクが組み合わさると、攻撃者はネットワーク内を横方向に移動できるようになります。そして攻撃者は、目的の重要アセットを狙うための完全な攻撃シナリオを確立することができます。下の画像には、この一連の動きが示されています。1998年のスティーブン・セガールの映画のような名前ですが、脆弱性をつなぎ合わせることをキルチェーンと呼びます。
高価なものをどこに置くか
私たちはまだネットワークにパッチを当てたいと願っています。しかし、少し回り道をして、本質的な数学的概念を説明し、それがIoTアプリケーションの安全性を確保するためにどのように使われるかを示唆する必要があります。
IoTのシナリオの一例として、通信するセンサーの大規模な集合が使用されます。ワイヤレスセンサーネットワーク（WSN）は、山火事から森林を守る場合（湿度、温度、気圧などの様々な環境要因に敏感なセンサーを配置する場合）、多くの機械が一体となって動作する産業アプリケーションを監視する場合、輸送ネットワークを調整する場合など、多くの場面で展開されます。以下の[1]の図は、11ノードのWSNを示しています。ノード番号1は、ネットワークを制御し、ネットワークから情報を集中的に収集するため、他のノードとは異なるマークが付けられています。
WSNは、他のコンピュータネットワークと同様、攻撃の標的になり得ます。私がアイスクリーム工場を経営しており、競合他社は私がミントチョコレートチップを作る温度を知りたがっているとしましょう。ここでどうやってネットワークを守ればいいのでしょうか？
ネットワークノードの中には、他のノードよりもインテリジェントなものがあります。例えば、ネットワーク上でやり取りされる情報（ネットワークパケット）の内容を検査し、悪意のあるパケットがあればアラートを出すといったモニタリング機能を持つことができます。この種のアプリケーションはリンクモニタリングシナリオと呼ばれます。
WSNのすべてのノードをモニタリングノードにすることは現実的ではありません。ノードあたりの実際のコストとエネルギー消費の点で、コストが膨れ上がってしまいます。例えば、ノードが広大な森林に広がっていて、バッテリーで動作しているとします。その場合、頻繁にバッテリーを交換する必要が出てくるでしょう。それよりもエネルギーを節約できるノードを配置すれば、生活はずっと楽になります。すべてのノードをスマートにして、電力を消費させ、高価にすることは、良い方法とは考えられません。
ここで、ネットワーク内のどのノードが最も他のノードを「見ている」のかを考えてみましょう。下の図も[1]から引用したもので、赤色で示されたモニタリングノードの一部を示しています。
グラフ理論では、グラフ全体を可能な限り「見る」ことができる（すなわち、接続されている）ノードの選択を、グラフの最大頂点被覆（MVC）と呼びます[https://en.wikipedia.org/wiki/Vertex_cover]。
MVCを求めるのは簡単な計算作業ではありません。技術的にはNP困難に分類される問題です。このような問題には、検証は簡単だが（簡単とは、解が成り立つかどうかを「多項式時間」で比較的速くチェックできることを意味します）、見つけるのが難しい（迅速な、つまり「多項式時間」で見つけることができない）解が存在します。
ここで量子計算の登場です。量子アルゴリズムを使ってMVC問題の近似解を求めることができます！
量子パッチの適用
さて、元の問題であるパッチ管理に戻りましょう。我々のゴールは、コンピュータネットワークにどのパッチを適用すれば最も多くキルチェーンを破壊できるかを特定することです。
数学的グラフは量子アルゴリズムが好むデータ構造です。それらには、グラフを分割するアルゴリズムや、グラフの中を検索するアルゴリズムなどがあります。
我々が苦境を表現するために使っているグラフは、技術的には2部グラフとして知られています。つまり、2つの異なるタイプ（アセットと脆弱性）のノードの集まりで、エッジによって接続されています。エッジは、攻撃者があるアセットから別のアセットへ、そのアセットで利用可能な脆弱性を悪用して移動する能力を表しています。
上で示したキルチェーンを二部グラフで表してみましょう。1,4,8という数字は特定の脆弱性を表し、特に意味はありません。ただ、既知の脆弱性リストの中から特定の脆弱性を選んだと想像してください。
このグラフから脆弱性とアセットを繋ぐエッジをすべて取り除きたいとします。これは、すべてのアセットにすべてのパッチを適用し、すべてを100％セキュアにしたいと言っているようなもので、それは現実的ではありません。そこで、キルチェーンを断ち切るような、脆弱性に優先順位をつける戦略を見つける必要があります。この単純な例では、脆弱性4を排除することでキルチェーンが途切れます。
これを見るための方法を紹介しましょう。この単純な例のためにグラフをさらに修正するのは奇妙に思えるかもしれませんが、後々より複雑なシナリオで役に立つことがわかります。まず双対グラフを定義しましょう。
双対グラフは脆弱性に注目し、それらが「元の」グラフのアセットを介してつながっている場合、それらを直接つなげます。これが今回の例の双対グラフです：
脆弱性4を取り除けばチェーンが断ち切られるという以前からの直感は、今やより明白なものとなり、1から8への移動は不可能となります。
もっと複雑なグラフだったら？
より多くのアセットと脆弱性を持つ、より複雑な例を考えてみましょう。何十万ものノードを持つ実際のネットワークに比べれば、まだおもちゃのモデルに過ぎませんが、すでに視覚的に複雑になっています。
これを双対グラフに変換すると以下のようになります：
ここでは単純化のため、無向グラフを作成しました。これは、方向に関係なく連鎖を断ち切り、最もよくつながっている脆弱性を優先するためです。またその方が作業が楽になり、単純なものから始めて徐々に複雑さを導入していく方が良いことも多いでしょう。多くの物事はそのままでは複雑なのです。
このグラフを見ても、どのノードを削除すれば最もキルチェーンを断ち切れるかは明らかではありません。ではどうすればよいのでしょうか？もちろんMVCを見つけることです！
双対グラフのMVCは、どのパッチを適用すれば最も多くのパッチ未適用のノードを互いに切り離し、脆弱性の連鎖を防ぐことができるかを教えてくれます。つまり、キルチェーンを断ち切ることが可能です。
この場合、青でマークされたノードがMVCソリューションを示しています。最小のコストで最大の防御を得るためには、これらのパッチを適用すべきです。
この解は2部グラフの形に戻すことができ、以前よりもずっと単純な形を示します。重要なのは、ある脆弱性から別の脆弱性へとアセットを経由して移動することは不可能だということです。チェーンは切れているのですから。
MVCと量子：Classiqの解法
これでサイバーセキュリティの問題に取り組む数学的な方法ができました。リンクモニタリングの例でも、キルチェーンの例でも、重要なのはMVCを見つけることです。簡単ですね。
すでに述べたように、問題はMVCを見つけることがNP困難なことです。実際の企業ネットワークには10万以上のホストが存在する可能性があるため、これは一般的に解決困難な問題です。
近似的な最大頂点被覆の探索は、量子コンピュータが取り組む組合せ最適化問題のクラスの主力である量子アルゴリズムを使えば、量子コンピュータ上で指数以下の時間で行うことができます。それがQAOA（量子近似最適化アルゴリズム）です。
MVCは組み合わせ最適化問題の典型的な例です。その難しさは、アイテムの組み合わせの数が非常に多いことに起因します。特定の組み合わせを選択する際には、通常、いくつかの制約を満たす必要があり、選択方法をスマートにするための十分な構造が問題には存在しません。結局、あらゆる可能性をチェックして、うまくいくものを見つける必要が生じます。つまり、解を見つけるには、問題の大きさに比例して指数関数的な時間がかかります。
QAOAを使えば、少なくとも厳密解ではなく近似解を求めることを厭わなければ、それよりも速く、あるいは指数以下の速さで解くことができます。ここではQAOAについて深く説明はしないものの、もし希望される読者が多ければ（ClassiqのSlackサーバーに連絡してください）、将来QAOAについて説明するかも知れません。またオンラインで多くのレビューを読むことができます。例えばこちら[https://arxiv.org/abs/2306.09198]。
QAOAを使った組合せ最適化問題への取り組みは、Classiqプラットフォームが得意とするところです。ここでは3つの簡単なステップを踏む必要があります：
1.Classiqの組合せ最適化機能を使って量子モデルを定義する
2.Classiqエンジンを使ってパラメータ化された量子回路を生成する
3.Classiqプラットフォーム内で回路を実行し、解を表す最適なパラメータを得る
QAOAとグラフを含むClassiqモデルを構築する手法は、標準的なオープンソースのツールと互換性があるため、極めて自然です。Classiq Python SDKを使用する場合、ネットワークグラフはまずnetworkxライブラリで構築されます。 次に最適化問題を定義しますが、ここでは様々な最適化言語が存在します。Pythonエコシステムでこれを行う汎用的で表現力豊かな方法の1つは、PythonのPyOmo言語 [http://www.pyomo.org/]を使うことです。PyOmoは強力でリッチであり、ユーザーは多数の最適化モデルを表現することができます。ユニークなことに、PyOmoはClassiqモデル[https://docs.classiq.io/latest/tutorials/advanced/optimization/]と緊密に統合されているのも特徴です。
次の画像は、Classiqプラットフォームによって合成された回路で、単純な双対ネットワークの近似MVCを見つけています。この回路は実際の量子ハードウェアやClassiqプラットフォームのシミュレータ上でボタンをクリックするだけで簡単に実行できます。
ぜひ、皆様もご自身でお確かめください。platform.classiq.ioへのへの登録は現在完全無料です。Classiqで利用可能なサイバーセキュリティ関連のサンプルモデルが用意されています。量子シミュレータと、複数のハードウェアプラットフォームの両方にアクセスできます。特定のハードウェアターゲット用に回路を書き直す必要はありません。
結論
サイバーセキュリティは、コンピュータネットワークに大混乱を引き起こし、コスト高や危険な混乱を引き起こす可能性のある、無数の隠れた問題を抱えています。これらの課題のいくつかは、数学的に定式化し、計算ツールを用いて取り組むことが可能です。
私たちが日常生活で依存している現代のコンピューターネットワークの規模は計り知れないものがあり、サイバーセキュリティにおける計算問題のいくつかを解決することは、通常の計算リソースでは不可能です。
幸いなことに、量子計算には解決策を見つけることを可能にするツールがありますが、これらの解決策を探索する量子ソフトウェアを生成する方がより現実的かもしれません。
Classiqプラットフォームは、PyOmo言語のような最適化問題で使われる標準的なツールを使って、最先端の量子アルゴリズムを実世界の問題に適用するための最善かつ最も簡単な方法を提供しています。
