WEB API (つづき) プログラム言語へのラッパー 上記のリクエストと応答をプログラムが処理するためには JSON / XML とプログラム言語固有のデータ構造との相互変換が必要 そのためのライブラリが Wrapper 例: Twitter4j (http://twitter4j.org/ja/index.html) Twitter API を Java言語から利用するための wrapper Twitter が提供するデータ構造に対応したクラスの定義 リクエストを発行するためのメソッドなど ブラウザ上ではない, 独立したアプリケーションからでもWEBサービスの利用が可能 ex. さまざまなTwitterアプリケーション 最近はWEBサービスの利用頻度を制限するために, 登録キーを必須にして, それを基準にAPI利用を制限することが多くなってきた ----------------------------------------------------------- HTTP での認証 (authentication) static なページでも使える認証 (HTTPで実装されている) Basic認証 と Digest認証 がある ◯ Basic認証 ディレクトリごとに, アクセスを許可するユーザ名とパスワードを設定 クライアントからアクセスがあったときは, それらを要求 正しければアクセスを認める Apache(ウェブサーバ) での例 ---- .htaccess ---- (対象ディレクトリに置くファイル) AuthType Basic AuthName "Authentication required" AuthUserFile /home/terada/FS/public_html/learn/auth/basic/.htpasswd AuthGroupFile /dev/null Require valid-user ---- .htpasswd ---- (.htaccess で指定した場所に置くファイル) testuser:$apr1$t9dvp/..$1dfGG8ZhVnOEsZtOY15qw0 ユーザ名と, パスワードをハッシュした文字列を格納 (この例では md5 ハッシュ関数を利用) 通信の実行例 (1) client -> server (保護されているディレクトリにあるファイルを要求) 0:GET http://pr.ice.uec.ac.jp/~terada/learn/auth/basic/index.html HTTP/1.1 後略 (2) server -> client (認証できないのでアクセス拒否 401) 1:HTTP/1.1 401 Unauthorized 1:Date: Thu, 22 Oct 2015 06:13:18 GMT 1:Server: Apache 1:WWW-Authenticate: Basic realm="Authentication required" (ここでBasic認証が必要であるとを示す) 中略 1:Connection: keep-alive 1: 1: 1: 1:401 Authorization Required 1: 1: ... (ここは人間向けの「認証が必要」というメッセージのHTML) 1: (3) ブラウザはユーザ名とパスワードを入力するためのポップアップを表示する (4) 人間がそれらを入力すると, client はふたたび server に GET を送る 0:GET http://pr.ice.uec.ac.jp/~terada/learn/auth/basic/index.html HTTP/1.1 0:Host: pr.ice.uec.ac.jp 中略 0:Authorization: Basic dGVzdHVzZXI6dGVzdHBhc3N3b3Jk (ここが人間が入力した認証情報) 0: (5) server -> client (認証に成功したのでコンテンツを返信する) 1:HTTP/1.1 200 OK 中略 1:Connection: keep-alive 1: 1: 1: 1: 1: 1:Content (index.html) 1: 1: ステップ(4)で client は認証情報を送っているが, この情報は base64 encoding であって, 容易に復号可能 % echo -n dGVzdHVzZXI6dGVzdHBhc3N3b3Jk | base64 -d testuser:testpassword httpの通信を傍受されると, パスワードが見えてしまう欠点 ◯ Digest認証 人間の入力したパスワードを, 平文ではなくハッシュ関数を使って暗号化して送る方式 利用者から見ると, ブラウザの振舞はBasic認証のときと同じ ---- .htdigest ---- (ユーザ名, realm(認証領域) と, MD5でハッシュしたパスワード) testuser:Learn Digest:ed5e2a4618444dba2be6c5496957d2cc 通信の実行例 (1) client -> server (保護されているディレクトリにあるファイルを要求) 0:GET http://pr.ice.uec.ac.jp/~terada/learn/auth/digest/index.html HTTP/1.1 後略 (2) server -> client (認証できないのでアクセス拒否 401) 3:HTTP/1.1 401 Unauthorized 3:Date: Thu, 22 Oct 2015 07:08:05 GMT 3:Server: Apache 3:WWW-Authenticate: Digest realm="Learn Digest", nonce="mR0SKKwiBQA=23b14f0da5e1cdc9d16ae396a0bb8da3730039ce", algorithm=MD5, domain="/~terada/learn/auth/digest/", qop="auth" 後略 このとき, サーバは要求する認証情報に関するデータを送ってくる nonce : ランダムな文字列を生成したもの (3) ブラウザはユーザ名とパスワードを入力するためのポップアップを表示する (4) 人間がそれらを入力すると, client はふたたび server に GET を送る 2:GET http://pr.ice.uec.ac.jp/~terada/learn/auth/digest/index.html HTTP/1.1 2:Host: pr.ice.uec.ac.jp 中略 2:Authorization: Digest username="testuser", realm="Learn Digest", nonce="mR0SKKwiBQA=23b14f0da5e1cdc9d16ae396a0bb8da3730039ce", uri="/~terada/learn/auth/digest/index.html", algorithm=MD5, response="9783d6d1cc4493ddbd5375ef7c6dcccc", qop=auth, nc=00000001, cnonce="9daa8c2915cbeaeb" 2: client は, 人間が入力したユーザ名 人間が入力したパスワード サーバからの nonce クライアントが作成した cnonce (ランダム文字列) を暗号化して, response としてサーバに送る サーバは 保存されている .htdigest から正しいresponseを求め, response と比較する. 一致したら認証成功. (5) server -> client (認証に成功したのでコンテンツを返信する) 3:HTTP/1.1 200 OK 後略 クライアントによる response の計算を実際に計算してみる (RFC 2617) A1 = testuser:Learn Digest:testpassword (人間の入力内容) A2 = GET:/~terada/learn/auth/digest/index.html MD5(A1) ed5e2a4618444dba2be6c5496957d2cc nonce mR0SKKwiBQA=23b14f0da5e1cdc9d16ae396a0bb8da3730039ce (サーバから入手してある) nc 00000001 cnonce 9daa8c2915cbeaeb (クライアントが生成) qop auth MD5(A2) 69cb0936b11dbc72ef80069036a89fdf response = MD5(MD5(A1) ":" nonce ":" nc ":" cnonce ":" qop ":" MD5(A2)) MD5(ed5e2a4618444dba2be6c5496957d2cc:mR0SKKwiBQA=23b14f0da5e1cdc9d16ae396a0bb8da3730039ce:00000001:9daa8c2915cbeaeb:auth:69cb0936b11dbc72ef80069036a89fdf) 9783d6d1cc4493ddbd5375ef7c6dcccc これをサーバは同じ方法で正解をもとに計算して比較する - ネットワーク上を平文のパスワードが流れない - 平文のパスワードは人間の頭の中だけにあればよい cnonceの必要性 attackerが通信を横取りして、常に同じnonceを送るようにすると、 attackerは辞書攻撃によって複数のパスワードを少ない労力で破れることになる。 (その唯一nonceで辞書をハッシュしておき、返信のハッシュと比較する) ----------------------------------------------------------- OAuth ウェブサービスで, データへのアクセス権限の一部を移譲するための仕組み (認可) 3人の登場人物 - Service Provider データを保持しているサービス (例: Twitter) - User Service Provider の利用者. 自分の認証情報を持っている. - Consumer ユーザの代わりにService Providerの一部の機能を実行するサービス. そのためにユーザのアクセス権限の一部が必要. ウェブサービスの場合 (例: Twitterに連携した各種サービス) 独立したアプリケーションの場合 (例: Twitterクライアント) 認証情報(パスワードなど)をConsumerに渡すのは望ましくない 「全権委任」になる 機能の一部だけを移譲することができない (例: タイムラインの読み出し) 最悪の場合, パスワード変更でアカウント乗っ取り 認可の取消しが難しい 手順 0. Consumer は事前に Service Provider に登録しておく Consumer Key, Consumer Secret 1. User が Consumer にアクセス 2. Consumer は User を Service Provider にリダイレクト 3. User は Service Provider にログインし, Consumer の要求するアクセスを認可 4. 認可情報が Consumer へ渡る 5. Consumer は認可情報と引き換えにアクセストークンを入手する Access Token, Access Token Secret 6. Consumer は Service Provider を利用 Consumer Key, Consumer Secret, Access Token, Access Token Secret ------------------------------------------------------------------------- P2P の概念 ----------------------------------------------------------- 典型的な問題 (typical task) 「ある条件をみたすホストを探す」 (to look up a host which meets some requirement) 「条件」-- 例: あるファイルを持っている (requirement -- e.g. the host keeps a certain file) 「探す」-- 接続するのに必要な情報を入手する (look up -- get information to connect to the host TCP/IPでは, (IP アドレス, ポート番号)を知る ((IPaddr,port) for TCP/IP) ----------------------------------------------------------- 完全な分散システム (distributed system) ノードが対称 (symmetric nodes) 中央制御,階層がない (no central control, no hierarchies) 参加離脱の管理なし (no control on join and leave of nodes) scalability 台数が増加しても動作する アドホック性 (ad hoc) (参加離脱の自由) (unconstrained join and leave) 耐障害性 (resistance for failures) (単一障害点なし) (no single-point-of-failure) ----------------------------------------------------------- P2P の歴史 (histories) 1999 Napster 楽曲のメタデータだけをサーバに集約 (keep metadata of music files on a server) メタデータ - データに関するデータ ここでは楽曲のタイトル, ミュージシャン, ... コンテンツ公開は自分のノード上でOK (music files are placed on users' machines) コンテンツの取得はノード同士で (transport files between user machines) 著作権問題から2001/07にサーバを停止 (server was closed by copyright problems) 2000 Gnutella ファイル共有 (file sharing) サーバなし (no servers) 2001 Kazaa ファイル共有 (file sharing) 2001 BitTorrent ファイルの配信 (delivery of files) 2002 Winny ファイル共有 (file sharing) 2004 Share ファイル共有 (file sharing) ----------------------------------------------------------- 探索の問題 (searching files) キーから実体を探す (search an item from the key) (ファイル名からファイルの所有ホストを探す) (i.e. search a file from the name of the file) Three ways to keep information: (1)メタデータとデータを同じホストに (keeping the data(item) and the metadata(key) on a server) 普通のファイルサーバ, uploader (usual file servers) (2)メタデータだけを集約 - hybrid P2P (collect only metadata on a server) データは各ノードに - Napster (data files are located on users' node) 配信の負荷軽減 (the load to deliver files are distributed) 公開が簡単 (easy to share files - only upload the metadata) (3)メタデータも分散 - Pure P2P (metadata is also distributed) (3a) unstructured ホストは random graph で結合 - 特にルールがない (nodes are connected without any rules) キーの割り当てもランダム (keys are distributed without rule) あるファイルをどのノードが管理するか (i.e. which node will keep a file is not determined) 参加離脱の管理コストが低い (low administration cost for joins/leaves) (3b) structured キーをホストに割り当てる方法が決まっている (rules to assign keys to hosts) 効率の良い探索が可能 (efficient lookup is possible) 参加離脱の管理コストが発生 (administration cost for joins/leaves) 探し方 (the search) unstrucured flooding (Gnutella) 方向づけ (FreeNet) structured DHT(Distributed Hash Table) (Chord, Pastry, ...) =========================================================== Small World "Collective dynamics of 'small-world' networks" Duncan J. Watts and Steven H. Strogatz Nature 393, 440-442 (4 June 1998) Small World experiment (Wikipedia) ======================================================================= The small world experiment comprised several experiments conducted by Stanley Milgram examining the average path length for social networks of people in the United States. The research was groundbreaking in that it suggested that human society is a small world type network characterized by short path lengths. The experiments are often associated with the phrase "six degrees of separation", although Milgram did not use this term himself. Basic procedure 1. Though the experiment went through several variations, Milgram typically chose individuals in the U.S. cities of Omaha, Nebraska and Wichita, Kansas to be the starting points and Boston, Massachusetts to be the end point of a chain of correspondence. These cities were selected because they represented a great distance in the United States, both socially and geographically. 2. Information packets were initially sent to randomly selected individuals in Omaha or Wichita. They included letters, which detailed the study's purpose, and basic information about a target contact person in Boston. It additionally contained a roster on which they could write their own name, as well as business reply cards that were pre-addressed to Harvard. 3. Upon receiving the invitation to participate, the recipient was asked whether he or she personally knew the contact person described in the letter. If so, the person was to forward the letter directly to that person. For the purposes of this study, knowing someone "personally" was defined as knowing them on a first-name basis. 4. In the more likely case that the person did not personally know the target, then the person was to think of a friend or relative they know personally that is more likely to know the target. They were then directed to sign their name on the roster and forward the packet to that person. A postcard was also mailed to the researchers at Harvard so that they could track the chain's progression toward the target. 5. When and if the package eventually reached the contact person in Boston, the researchers could examine the roster to count the number of times it had been forwarded from person to person. Additionally, for packages that never reached the destination, the incoming postcards helped identify the break point in the chain. Results Shortly after the experiments began, letters would begin arriving to the targets and the researchers would receive postcards from the respondents. Sometimes the packet would arrive to the target in as few as one or two hops, while some chains were composed of as many as nine or ten links. However, a significant problem was that often people refused to pass the letter forward, and thus the chain never reached its destination. In one case, 232 of the 296 letters never reached the destination.[3] However, 64 of the letters eventually did reach the target contact. Among these chains, the average path length fell around 5.5 or six. Hence, the researchers concluded that people in the United States are separated by about six people on average. And, although Milgram himself never used the phrase "six degrees of separation", these findings likely contributed to its widespread acceptance.[1] In an experiment in which 160 letters were mailed out, 24 reached the target in his Sharon, Massachusetts home. Of those 24, 16 were given to the target person by the same person Milgram calls "Mr. Jacobs", a clothing merchant. Of those that reached him at his office, more than half came from two other men.[4] The researchers used the postcards to qualitatively examine the types of chains that are created. Generally, the package quickly reached a close geographic proximity, but would circle the target almost randomly until it found the target's inner circle of friends.[3] This suggests that participants strongly favored geographic characteristics when choosing an appropriate next person in the chain. ======================================================================= (Natureの論文の冒頭) "... Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks rewired to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them small-world networks, by analogy with the small-world phenomenon (popularly known as six degrees of separation)." 2016-10-28 Regular network regular ring lattice (Fig. 1, left) Random network (Fig. 1, right) rewiring probability: p p = 0 -> regular p = 1 -> random 0 < p < 1 -> intermediate region characteristics of network L(p): characteristic path length number of edges in the shortest path between two vertices, averaged over all pairs of vertices (最短距離の平均) C(p): clustering coefficient vertex v has kv neighbours. at most kv(kv-1)/2 edges can exist between them. Cv denotes the fraction of these allowable edges that actually exist (隣接ノードの間にリンクがある割合) n: number of vertices k: number of neighbours assumption: sparse, connected graph n >> k >> ln(n) >> 1 Fig. 1: n=20, k=4, ln(20)=3 (p->0) L ~ n/2k >> 1 large world C ~ 3/4 highly clustered (p->1) L ~ Lrandom ~ ln(n)/ln(k) small world C ~ Crandom ~ k/n << 1 poorly clustered Fig. 2 There is a broad interval of p: L(p) is almost as small as Lrandom C(p) >> Crandom "small world network" short cut is important Table 1 examples of small world networks