United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,941,947
`
`Brown et al.
`
`[45] Date of Patent:
`
`Aug. 24, 1999
`
`USU0594 I 947A
`
`[54] SYSTEM AND METHOD FOR
`CONTROLLING ACCESS TO one
`ENTITIES i:N A COMPUTER NETWORK
`
`5.361621 M994 Cohen e_: a1.
`5371.852
`1211994 A«a_-was-o
`5333355
`9/1995 PW“ H ='- v
`5396.626
`3:199: Nguyen _
`
`.
`
`Inwntarsz E°'::nh'l;rBgmR:“¢}nE‘:;Vl;:‘::°fh:f£hG'
`
`Assignee:
`
`l\-ficmsnfl Corporation. Redmond.
`wash‘
`
`Appl. No.: 081516.573
`
`Aug. 13. 1995
`
`Filed:
`In . Cl.‘
`Uis Cl
`me of Search
`3
`.
`95200
`
`cuss 1-mo
`-mwns
`395500.55. 200.56.
`.2 .
`.
`.
`.
`.
`7102:2695
`
`’
`
`‘.3’.
`
`.
`
`{List continued on next page.)
`omen PU'BLlCA'I'IONS
`
`Operating System Concepts. Fourth Edition. Abraham Sil-
`berschatz and Peter B. Galvin. pp. 36l—380. 431-457.
`
`_
`_
`©1994-
`Inside Windows NT. Helen Custer Foreword by David N.
`Cutler. The Object Manager and Object Seciirity. Chapter
`T"’°°- Pl’- ‘‘9”*‘“- @993-
`So .
`.
`. Just What is this First Class Thing Anyway? [visited
`f:‘b:u',g‘C'h°::l’)_“‘""‘”°‘i°“'°"‘“°"“““’°"“""°"“’ESD’FC’
`.
`.
`.
`.
`.
`Coltori. Malcolm. “Re'pl|cated Data in a Distributed Envi-
`roi:Ii'nent." IEEE (1993).
`
`References Cited
`
`(List continued on next page.)
`
`U'S' PATENT DOCUMENTS
`111950
`.
`4.134.200
`‘H1981
`4.23-0.]'i'6
`231934
`4.432.051
`LFI985 Ba.xter.1letaJ.
`4.493.024
`4.799.153 mess Hann elal.
`'
`4_1r99_;5.5
`H1939 sham 9. ,1 _
`4.300433
`H1939 Agmwaj e;a|._
`4.853.: 17 M98‘; Dichim er. a1.
`4399-136
`231990 Beard cl 33-
`-
`4-9145"”
`‘W999 33”“ '4 "1 -
`5.0?9.'l6S
`li'l99'2 Nakiliiiiia .
`5.113.499
`511992 miimey er al.
`5 H0 639 M9” Kohayasbi
`5:151:95.)
`9,1992 Johnna El
`5J3-U90
`2;l993 Fast 6‘ at _
`,
`5 _24-L575
`931993 92." cl ,1.
`5.257.369 W1993 Skeen et ai..
`5.265250
`Il!l9';I3 Andrade et a].
`5291.59?
`3«'1994 Shorter 8! 21-
`-
`5-3m-49"
`4”994 D3""d9°“ 9' 31-
`5’32l'M1
`$1994 Em '3 at '
`5.329.6l9
`"H199-1 Page et 2]..
`I
`5_341-4??
`sag“ FEM“ cl 3].
`5341632
`911994 Fiiepp elal._
`5355.49?
`1011994 Cohen-Levy .
`
`I
`
`.
`
`-
`
`3-asriss
`sssxiss
`
`3951133
`ssorzs
`
`395!138
`
`Primarjv Eumii'ner—El1is B. Ramirez
`Ariamey, Agent. or Fa‘rm—Lcydig. voit & Mayer. Ltd.
`
`[5?]
`
`ABSTRACT
`
`_
`_
`=“-°°¢S"1Bh‘5°f “5“5°fa'-‘°“‘P“‘°f "°“'*’°‘kW'"1 1‘¢5P°°"°
`data entities are specified by a retationaidanabase stored on
`one or more security servers. Application servers on the
`network that provide user access to the data entities generate
`queries to the relational database in order to obtain access
`rights lists of specific users. An access rights cache on each
`-
`-
`v
`‘
`aPP1'°‘"'°" 53"“ cadm’ '1" axe.“ "gm. “S55 °f the "M5
`that are connected to the respective application server. so
`that user acoess rights to specific data en_t.ities can rapidly be
`determined. Each tiser—specific access rights list includes a
`series of category identifiers plus a series of access rights
`values. The category identifiers specify categories of data
`entities to which the user has access. and the access rights
`values specify privilege levels of the users with respect to
`the corresponding data entity categories. The privilege lev-
`els are oonverted into specific access capabilities by appli-
`.
`.
`.
`-
`canon programs running on the application servers.
`
`66 Claims, 10 Drawing Sheets
`
`: 1. .'..s- Id-\l.'| n-_uuI.
`i.~ r.1.~.-;. \ 3-3'1-'5 n.- u-.'.
`J'£(I \ I'.' I II(InE0?
`
`Facebook's Exhibit No. 1012
`Page 1
`
`

`
`5.-'1-23.003
`5.434.994
`5.444.848
`5.455.932
`5.463.625
`5.4-'Jr'3 599
`5.475.819
`5.4815320
`5.-183.652
`5.490.270
`5.491 .800
`5.491 .81?
`5.491.820
`5.49"}.-I63
`5.499.342
`5.5C0.9Q9
`5 .5 13.314
`5526.491
`5530.852
`5544.313
`5.544.327
`5.548.?!-1
`5548.726
`5 .5 51 .508
`5.553.239
`5.553242
`5559.969
`5564.043
`5.572.643
`5.581353
`5592.611
`5.596.579
`5.596344
`5.608.865
`5.603.903
`5.61".-‘.568
`5.617 .570
`5.619.632
`5.650.991
`5.666.519
`5,6‘.-‘S323
`5.6'35.'i96
`5.696.395
`SJ".-‘«1.668
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`U.S. PATENT DOCUIVIENTS
`Beneau .
`631995
`'.-‘31995
`Shahem el al.
`831995
`Johnson et al. .
`1031995
`Major et al. .
`1031995
`Ynsrehi .
`.
`1231995
`Li et a1.
`1231995
`.
`‘Miller et al.
`131996
`Loucks er. al. .
`.
`Sudama et a1.
`131996
`Devarakonrla et al.
`231996
`2.31996
`Goldsmith et a1.
`.
`2.31996
`Gopal et al.
`.
`2.31996
`Belove et al. .
`331996
`Stein et al.
`.
`331996
`Kunbarn et al.
`331996
`Dickinson .
`-131996
`Kadasamy et al.
`Wei .
`631996
`631996
`Meslne et a]. .
`Shnchanal e1 2].
`831996
`831996
`Dan et al.
`.
`831996
`Akizawa et al.
`831996
`Pettns .
`931996
`Pettns et al. .
`931996
`Heath et al. .
`931996
`Russell et al.
`931996
`Jennings .
`Sieferr. .
`1031996
`1131996
`Judson. .
`1231996
`.
`Terry et a1.
`13199?
`Midgely et al.
`13199?
`Yasrebi .
`Dao .
`13199".-'
`33199?
`Midgely et al.
`33199?
`Prasad el al.
`.
`43199?
`Ault el al. .
`.
`43199?
`Russell et al.
`43199?
`Lamping et al.
`‘F3199?
`Daley .
`93199‘.-'
`Hayden .
`.
`El-zrot el :11.
`103199’?
`1031997
`Hodges et a1.
`123199?
`Hemphiil .
`631998
`Choqtlire el al.
`
`_
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5,941,947
`Page 2
`
`OTHER PUBLICATIONS
`
`Coulouris et a1.. “Distributed Transactions." Chapter 1:1 of
`Distributed S_v.srcm.t Concepts and Design 2"‘ Ed.. 409-421
`1 1994).
`Cox. John. "sybnse Server to Add Complexity User for
`Challenge with Data Replication." Communication No. 483
`(1993).
`Eel-zerson. Wayne. “Users Give Green Light for Replica-
`tion." Ne-tworit World (Jul. 19. 1993).
`Edelstein. Herb. "The Challenge of Replication." DBMS vol.
`8. No. 4. 68 (Apr. 1995).
`Edelslein. Herb. “Microsoft and Sybase are Adding their
`Unique Touches to SQ] Servers.“ irtformatiort Week. No.
`528. 62 (1995).
`Edelstein. Herb. "Replicating Data." DBMS vol. 6. No. 6. 59
`(Jun. 1993).
`Gouhle. Michael. “RDBMS Server Choice Gets Tougher."
`Network Hbrtd. 52 (May 23. 1994).
`Heylighen. Francis. "World-Wide Web: A Distributed
`Hypermedia Parndigln for Global Networking." Proceed-
`ings of the SHARE Europe Spring Conference. 355-368
`(1994).
`International Telecommunications Union. CCHT Blue Book
`vol‘. VH1 Dara Cornmtmicariort Networks Director}; 3-18
`(1989).
`King. Adrian. ‘The User Interface and the Shell.“ inside
`Windows 95, Chapter 5 (1994).
`Pallallo. John. “Sybasc Lays Ont Blue Print for Client!
`Sewer Networks." PC Week vol. 9. No. 461. 6 (1992).
`PR Newswire Association. Inc.. “America 0n—1ine Publicly
`Previews World Wide Web Browser." Financial News Sec-
`tion {May 9. 1995).
`Quereshi. "The Efiect of Workload on the Perfonnance and
`Availability of Voting Algorithms." IEEE (1995).
`Rexford. Jennifer. "Window Consistent Replication for
`Real-Time Applications." IEEE (1994).
`Riclunan. Dan. “Sybase to Enhance RDBMS.“ Open System
`Tada); No. 111 (1992).
`Terry. Douglas. "Session Guarantees for Weekly Consistent
`Rcplicated Data." IEEE (1994).
`Wang. Yongdong. "Data Replication in a Distributed Het-
`erogenous Database Envlronrnent.“ IEEE‘ (1994).
`
`Facebook's Exhibit No. 1012
`Page 2
`
`

`
`U.S. Patent
`
`0..UA
`
`9mM.
`
`Sheet 1 of 10
`
`5,941,947
`
`ACCESS
`msms
`DATABASE
`
`Facebook's Exhibit No. 1012
`Page 3
`
`

`
`U.S. Patent
`
`WAm,2amuA
`
`Sheet 2 of 10
`
`5,941,947
`
`fitzummQQ D_390ou_.Cmm9E:8__&<
`
`:30»
`
`
`
`D_$5..._C3o3_o
`
`Facebook's Exhibit No. 1012
`Page 4
`
`

`
`U.S. Patent
`
`Aug. 24, 1999
`
`5,941,947
`
`Access Control Matrix .300
`
`\
`Node 1
`
`Node 0
`
`XXXX
`
`XXXX
`
`W
`
`I
`
`: xxxx ‘:
`\
`I
`
`xxxx
`
`User Privilege Level
`
`Facebook's Exhibit No. 1012
`Page 5
`
`

`
`U.S. Patent
`
`Ang.24, 1999
`
`Sheet 4 of 10
`
`5,941,947
`
`Token 1
`
`Token 2
`
`Security Token
`
`Nome (Content Category)
`
`Internet
`
`‘lB——and-— Older
`
`2 3
`
`Facebook's Exhibit No. 1012
`Page 6
`
`

`
`U.S. Patent
`
`Aug. 24, 1999
`
`Sheet 5 of 10
`
`5,941,947
`
`.300”-.___
`
`Ailsysops
`
`Supersysops
`
`Registration /Sign— Up
`
`18- and- Older Access
`
`Facebook's Exhibit No. 1012
`Page 7
`
`

`
`U.S. Patent
`
`an...A
`
`WM”,
`
`Sheet 6 of 10
`
`5,941,947
`
`mwqmfi<0m:._o_mm88<L
`
`
`
`
`
`
`
`030...coxohIycaouoa.m_n_o._.coxohIn__..o._o033.on_Eo2..a_._o._o
`
`
`
`
`
`
`
`%nxqooo
`
`.02.“oo<Low:9a_..o._u
`
`Facebook's Exhibit No. 1012
`Page 8
`
`

`
`U.S. Patent
`
`Aug. 24, 1999
`
`Sheet 7 of 10
`
`5,941,947
`
`STEPS TAKEN BY SECURITY SERVER
`IN RESPONSE TO ACCESS RIGHTS
`QUERY FOR USER X
`
`ACCESS GROUP—MEMBER TABLE
`TO IDENTIFY GROUPS IN WHICH
`USER X IS A MEMBER
`
`ACCESS GROUP—TOI<EN TABLE
`TO IDENTIFY CONTENT CATEGORIES TO
`WHICH USER X HAS ACCESS BY VIRTUE
`OF BEING IN THE GROUP/S IDENTIFIED
`IN STEP 702, AND OBTAIN ACCESS
`RIGHTS TO SUCH CONTENT CATEGORIES
`
`ACCESS ACCOUNT-TOKEN TABLE
`TO OBTAIN ANY ADDITIONAL
`RIGHTS THAT HAVE BEEN GIVEN
`TO USER X
`
`SORT TOKENS OF IDENTIFIED CONTENT
`CATEGORIES IN ASCENDING
`NUMERICAL ORDER
`
`RETURN SORTED TOKENS AND
`CORRESPONDING ACCESS RIGHTS
`TO CALLING SERVER
`
`Facebook's Exhibit No. 1012
`Page 9
`
`

`
`U.S. Patent
`
`9991MoneuA
`
`Sheet 8 of 10
`
`5,941,947
`
`
`
`uuimmxutzumm
`
`
`
`
`
`._o.Cmmou_?_umxCo.uE_o
`
`
`
`Totem9____8550Log
`
`
`
`
`
`
`
`
`
`5..50:0mEo_m_mmuou<
`
`
`
`
`
`mEm_mmmwuuqB_._m_w_mmooo<u_._<mcov_o._.._$mDxgum:Mnuoo
`
`
`
`
`
`_.._o.._o._.Iacaouoq
`
`22:
`
`~32.
`
`
`
`cuxopIasoé3.690L:_ou_._mE:z
`
`
`
`.2m..:._m_mmmmuu<+m:3_o._.
`
`xLaw:
`
`oomhas.8
`
`
`
`..0mD._O_.
`
`
`
`
`
`Exam.mmouu<u.._<mcoxo._.comEm:
`
`
`
`
`
`Facebook's Exhibit No. 1012
`Page 10
`
`

`
`U.S. Patent
`
`mu..,M
`
`Sheet 9 of 10
`
`5,941,947
`
`
`
`Paom16993208.8zmooofi:3oo.E
`
`
`
`
`
`
`
`N3.Illllla
`
`
`
`ocooomEm_mmmouua.
`
`Facebook's Exhibit No. 1012
`Page 11
`
`

`
`U.S. Patent
`
`Aug.24, 1999
`
`Sheet 10 of 10
`
`5,941,947
`
`GetAccountRights(USER X, TOKEN Y)
`
`CHECK CACHE
`FOR USER’S
`ACCOUN T N O.
`
`'
`
`CACHE
`HIT
`
`2'0 .72
`
`HAS QUERY
`THREAD BEEN
`STARTED
`
`INITIATE BINARY
`SEARCH OF CACHE
`ROW FOR TOKEN Y
`
`THREAD
`
`TOKEN NOT FOUND, BUT
`ROWIS NOT COMPLETE
`
`CHECK
`SEARCH
`RESULTS
`9
`
`TOKEN NOT FOUND,
`AND ROWIS COMPLETE
`
`RETURN CODE
`INDICATING THAT
`USER X CANNOT
`ACCESS TOKEN Y
`
`CHECK ADJACENT
`SLOTS IN CACHE
`FOR DUPLICATE
`TOKENS
`
`RETURN 16-BIT
`
`ACCESS RIGHTS
`VALUE OF USER X
`TO TOKEN Y
`
`Facebook's Exhibit No. 1012
`Page 12
`
`

`
`5 .94 I .947
`
`1
`SYSTEM AND METHOD FOR
`CONTROLLING ACCESS ‘ID DATA
`ENTITIIES IN A COMPUTER NETWORK
`FIELD OF THE. INVEl"lTION
`
`The present invention relates to computer networks in
`which access rights to data entities vary from user—to-user.
`More particularly. the present invention relates to database
`systerns for storing access rights information.
`BACKGROUND
`
`The present invention is directed generally to the problem
`of flexibly and elficiently controlling the access rights of a
`large number of users to a large number of objects or other
`data entities. The problem arises. for example. in the context
`of on-line services networks in which end users are given
`differing levels of access to different content entities. These
`content entities represent the services or "content“ of the
`network. as seen by end users. The content entities may
`include.
`for eltampie. bulletin board messages. mail
`messages. data files. folders. image files. sound files. mul-
`timedia files. exectrtable files. on-line services. connections
`to other networks. etc. An on-line services network of this
`type is described in copending US. Application Ser. No.
`081472.80? having the title ARCHITEJCIURE FOR SCAL-
`ABLE ON-LINE SERVICES NETWORK. filed Jun. 7.
`1995 (Now US. Pat. No. 5.774.668).
`‘The need to assign user-specific access rights to difierent
`content entities arises in a variety of situations. For example.
`it may be desirable to give some users access to certain
`“premium” services (such as specially-targeted investment
`newsletters). while limiting others users to some basic set of
`services. Further. it may be desirable to give certain users
`{such as system operators or administrators) the ability to
`modify. rename or delete certain content entities (such as
`bulletin board messages). while limiting other users to
`read-only access of such entities.
`Various techniques are known in the art for controlling
`user accesses to objects and other data entities. One
`technique. which is commonly used in file systems. involves
`the storage of an access control list (ACL) for each data
`entity to which access is to be controlled. The ACL for a
`given data entity will typically be in the form of a list of the
`users that have access to the data entity. together with the
`access rigits of each such user with respect to the data entity.
`Each t.i.I'ne a user requests access to the entity.
`the data
`entity's AC1. is searched to determine whether the requested
`access is authorized. Another technique involves the storage
`of a capabilities list for each user. The capabilities list for a
`y'ven user will typically include a list of the objects to which
`the user has access. together with the operations that can be
`perfonned by the user on each listed object. Both the ACL
`technique and the capabilities list technique are described in
`Silberschatz and Galvin. Operating System Concepts.
`Fourth Edition. Addison-Wesley Publishing Company.
`1994.
`With the increasing popularity of on-[inc services
`networks. and with the increasing need for such networks to
`provide limited user access to the Internet. it has become
`increasingly important to be able to provide large numbers
`of users with controlled access to large numbers of content
`entities. In the network described in the above-referenced
`application. for example. it is contemplated that the number
`of subscribers may be in the millions. and that the number
`of content entities may be in the tens of thousands. To
`provide flexibility. it is also desirable to be able to individu-
`alize the access rights of users.
`
`5
`
`2
`Although prior an access control techniques such as those
`summarized above are suitable in theory for flexibly con-
`trolling user access in large-scale on—line services networks.
`these techniques tend to produce prohibitively large quan-
`tities of access rights data. For example. in a network having
`nlillions of users. the access control list technique might
`produce access control lists that have millions of entries.
`These large quantifies of access rights consume large
`amounts of memory. and often take unacceptably long
`periods of time to search.
`A need thus exists in the art for a technique that is suitable
`for flexibly controlling the access of a large number of users
`to a large number of data entities. A need also exists to be
`able to flexibly and efliciently define new types of access
`operations as new on-line services and new content entities
`are created.
`
`SUMMARY
`
`In accordance with the present invention. there is pro-
`vided a system and method for controlling user access to
`data entities in a computer network. The data entities are
`preferably in the form of content objects of an on—line
`services network. although the system and method can be
`used to control access to other types of data entities.
`In a preferred implementation of an on-line services
`network in which the present invention is embodied. the
`content objects are stored on multiple application servers of
`the network. and represent the on—line services and service
`data that is accessible to users of the network. Examples of
`content objects include bulletin board system (BBS) mes-
`sages and folders. Chat conferences. download—and—run
`files. and service applications which implement specific
`on-line services. Users access these content objects by
`connecting to diflerenl application servers and correspond-
`ing services in the course of a logon session.
`Service applications running on the application servers
`implement various on-line services. such as Chat. Mail.
`BBS. F-TM {File Transfer Manager) and Mediaview. One
`on-line service. referred to as the Directory Service. main-
`tains a directory structure of the content objects that are
`accessible to users. with the content Objects forming nodes
`of the tree-like directory slrucn.I.re. By sending properties of
`these nodes to a client application running on the computer
`of an end user. the Directory Service provides the user with
`a hierarchical. navigable view of the content of the network.
`In accordance with the invention. diifuent users of me
`network (including both subscribers and system
`administrators) are given dilferent access rights with respect
`to different content objects. and can thus perform differing
`types of operations with respect to the content objects. For
`example. with respect to a given BBS folder. some users
`may be prevented from seeing or otherwise accessing the
`folder. some may be given read-only access to the contents
`of the folder. some may be given the capability to create new
`messages within the folder. and some may additionally be
`given the capability to delete andfor rename messages within
`the folder.
`In accordance with one feature of the present invention.
`the access rights of the users of the network with respect to
`the various user-accessible content objects are specified by
`access rights data that
`is stored within an access rights
`database. The access rights database is implemented as a
`relational database on one or more security servers. which
`are connected to the application servers by a local area
`network. The access rights data is stored within the rela-
`tional database in association with multiple content category
`
`Facebook's Exhibit No. 1012
`Page 13
`
`

`
`5 .94 I .947
`
`3
`identifiers. or “tokens.” which identify categories or group
`ings of content objects (such as "internal public data."
`"Internet public data.” and "18-and-older only data") for
`security purposes. The various content categories are pref-
`erably defined by system administrators. The content
`categories. rather than the content objects. serve the basic
`content units to which user access rights may be specified
`The use of content categories eliminates t.he need to store
`access rights data on a per—object basis. and thereby signifi-
`cantly reduces the quantity of access rights data that needs
`to be stored.
`
`The access rights data is preferably stored within the
`relational database in further association witl1 multiple user
`group identifiers. which identify user groups (such as
`“everyone.” “allsysops." and "guests";
`that have been
`fonned for Ute purpose of storing access rights data. By
`storing access rights data primarily on a per-user—group
`basis. rather than separately storing the access rights of each
`individual user. the use of user groups further reduces the
`quantity of access rights data that needs to be stored.
`The use of content categories and user groups advanta-
`geously allows access rights to be specified for large num-
`bers of users {typically millions) with respect
`to large
`numbers of content objects (typically thousands) willt a high
`degree of granularity.
`In accordance with another feature of the invention. the
`service applications running on the various application serv-
`ers initiate user-specific queries of the access rights database
`to obtain access rights lists of specific users. With each
`user—specific access rights query. the security server that
`receives the query accesses the access rights database and
`generates an access rights list which fully specifies the
`access rights of the user. This access rights list is returned to
`the application server that generated the query. and is stored
`within an access rights cache of the application server. The
`service which initiated the query can then rapidly determine
`the of access rights of the user with respect to specific
`content objects (as described below) by accessing its locally-
`storcd copy of the user‘s access rights list. Because a user
`may be connected simultaneously to multiple application
`servers of the on-line services network (when. for example.
`the user opens multiple services). the access rights list of a
`given user may be stored concurrently within the respective
`caches of multiple application servers.
`In accordance another feature of the invention. the access
`rights list of each user includes pairs of tokens and corre-
`sponding access rights values. Each token in the list iden-
`tifies a content category to which the user has at least some
`access rights. For example. a token of “S” in the list indicates
`that the user has access to all content objects which fall
`within content category 5. Each access rights value in the list
`specifies the access rights of the user with respect
`to a
`corresponding content category. The access rights values are
`preferably in the form of privilege level masks which
`specify one or more general privilege levels {such as
`“viewer.” "user." "host." “sysop." and "supersysop"}. These
`general privilege levels are translated into specific sets of
`access capabilities by the on—line service applications. For
`example. t.l1e BBS service may give users with sysoplevel
`privileges the capability to delete and rename BBS mes-
`sages.
`In accordance with another feature of the invention. when
`it becomes necessary for a service i running on an applica-
`tion serverj to determine the access rights of a user with
`respect to a specific content object. the service initially reads
`the object‘s token. which is preferably stored as a property
`
`4
`of a corresponding Directory Service node. This token
`specifies the content category to which the content object
`belongs. The service then generates an API (application
`proyarn interface; call. which causes the application server
`to search its access rights cache for the user's access rights
`list. and if found. to search the access rights list for the token.
`If the user's access rights list is not found. the APT initially
`generates a query of the access rights database (to fill the
`cache with the user‘s access rights list). and then begins to
`search the cache for the token. lfthe token is found. the AP]
`returns the corresponding access rights value to the service
`that generated the API call. If the token is not found. the API
`returns a code indicating that the user cannot access the
`content object.
`In accordance with yet another feature of the present
`invention.
`the relational. access rights database includes
`three tables. The first table is a group—I'nen:tber table which
`specifies the user groups and the members (i.e.. user
`accounts} of each user group. Each user of the network is a
`member of at least one user group. and may be a member of
`multiple groups. The second table is a group-token table
`which contains. for each user group. a group-based access
`rights list (in the form of a list of tokens and corresponding
`access rights values}. Each group—based access rights list
`specifies the group—base:d rights which are provided to all
`members of the respective group. The third table is an
`account—token table. which specifics. on a single-user basis
`( for certain users). additional rights that are to be added to
`the group-based rights of the user. Each user-specific entry
`in the account-token table is preferably in the form of a
`single token plus a corresponding access rights value.
`In addition to (or in place of) the account-token table. an
`exclusion table may optionally be irnpletnented to specify
`access rights that are to be taken away from the accounts of
`specific users. As with the account-token table. each user-
`specific entry in the exclusion table is preferably in the form
`of a single token plus a corresponding access rights value.
`The exclusion table is useful. for example. for taking away
`certain privileges of users who rnisttse certain services.
`Upon receiving a user-specific access rights quay. the
`security server initially accesses the group-member table to
`identify all user groups of which the specified user is a
`member. The security server then accesses the grouptolten
`table to obtain the group-based access rights list of each user
`group of which tl'te user is a member. The security server
`thereby identifies all of the rights the user has by virtue of
`being a member of one or more user groups. If the user is a
`member of multiple user groups. the multiple group-based
`access rights lists are combined so that the user is given all
`of the rights associated with all user groups of which the user
`is a member. The security server then accesses the account-
`token table to determine whether any additional
`(or
`"special“ t rights {in the forth of tokens and corresponding
`access rights values) have been added to the account of the
`user. If one or more entries exist in the account—token table
`for the user. these ent'.t'ies are combined with the user’s
`group-based rights to generate the user's access rights list.
`(For embodiments that include an exclusion table. if one or
`more entries exist for the user in the exclusion table. these
`entries are subtracted from the user's group-based rights.)
`The access rights list is then sorted such that the tokens of
`the list (and corresponding access rights values) are placed
`in numerically ascending order [to facilitate cache searches
`of the list}. and the sorted list is transmitted to the application
`server that generated the query.
`The system and method of the present invention advan-
`tageously enabled system administrators to flexibly control
`
`Facebook's Exhibit No. 1012
`Page 14
`
`

`
`5.94! .94‘?
`
`5
`user access to different "service areas" in order to achieve a
`variety of objectives. In accordance with a preferred mode
`of operation. when a new service area (preferably repre-
`sented by one or more nodes of the directory structure) is
`created. a security token may be assigned to the new service
`area to provide separate security for the area. A particular
`user. who may be either a subscriber to the network or a
`system ad.n1inist.ratoi'. may then be given sysop-type privi-
`leges (via the above-mentioned account-token table} to the
`new service area. By making different users sysops with
`respect to different service areas. the responsibility of moni-
`toring user-generated content is di_st1'1'buted among many
`different individuals. In accordance with another preferred
`mode of operation. content categories and user groups are
`formed so as to create many different communications
`forums (such as Chat conferences and BBS folders} for
`private correspondence among user-specified subgroups of
`users.
`
`BRIEF DESCREI-‘TION OF THE DRAWINGS
`These and other features of the invention will now be
`described with reference to the drawings of a preferred
`embodiment. which is intended to illustrate and not to limit
`the invention. and in which:
`
`FIG. 1 is a high level diagrain illustrating the general
`architecture of an on—line services network which provides
`access control in accordance with the present invention.
`FIG. 2 iuuslrales how the content of the on-line services
`network of FIG. 1 is preferably arranged within a tree-like
`directory structure of content nodes.
`FIG. 3A illustrates an access control matrix which
`specifies. for each user and for each node of the directory
`structure of FIG. 2. whether the user can access the node.
`and if so. what the level of access is. The notation “XXX?X"'
`in FIG. 3A represents a l6«bit access rights value.
`FIG. 3B illustrates a preferred basic set of privilege levels.
`and illustrates one possible assignment of access rights bits
`to the privilege levels.
`FIG. 4A illustrates how the aocess control matrix of FIG.
`3A is preferably compressed horizontally by the assignment
`of content nodes to content categories. with each content
`category identified by a numerical security token.
`FIG. 4B is a token definition table which illustrates a
`preferred basic set of security tokens (tokens 1-4}. and
`which illustrates examples of tokens (tokens 100 and 101)
`which may be added to accommodate specific data types.
`FIG. SA illustrates how the access control matrix of FIG.
`3A is compressed vertically by the assignment of users to
`user groups.
`FIGS. 5B is a group definition table which shows a
`preferred basic set of user groups. and which illustrates one
`possible assignment of group IDs to user groups.
`FIG. 6 illustrates a preferred relational database which is
`used to store access rights data in accordance with the
`present invention. Numerical values in FIG. 6 are examples
`of possible table entries.
`FIG. 7 illustrates a sequence of steps taken by one of the
`security servers of FIG. 1 when a database query is made for
`the access rights of a specific user.
`FIG. 8 illustrates the preferred process by which one
`application server queries a security server for the access
`rights of a specific user and then caches the access rights
`data returned by the security server. Also shown in FIG. 8
`are the basic structures used for hustling user-specific rows
`of the cadre.
`
`6
`FIG. 9 illustrates a preferred arrangement of the cache of
`FIG. 3. Numerical values in FIG. 9 oorrespond to the
`example table entries of FIG. 6.
`FIG. 10 illustrates a sequence of steps taken by an
`application server to determine the access rights of a specific
`user ("user X“) with respect to a specific tolten (“token Y“).
`Reference numbers in the drawings have three or more
`digits: the two least significant digits are reference numbers
`within the drawing. and the more significant digits indicate
`the figure in which the item first appears. For example.
`reference number 602 refers to an item which is first shown
`in FIG. 6. Like reference numbers indicate like or function-
`ally similar components.
`
`DETAILED DESCRIPTION OF A PREFERRED
`EMBODIMENT
`
`Described herein is a system and method for controlling
`the access rights of users of an on-line services network to
`content entities such as bulletin board messages. message
`folders. chat conferences. service applications. download-
`and-run files and data files. As will be recognized by those
`slcilled in the art. the system and method of the present
`invention are generally independent of the specific type or
`types of data entities to which access is being controlled. For
`example. the data entities could be low-level software andlor
`hardware resources such as threads. sernaphotes. memory
`segments and CPUs. It will funlter be recognized that the
`system and method of the present
`invention could be
`employed in any of variety of alternative nerworlzing
`environments. including file systems and operating systems.
`For convenience. the description of the preferred embodi-
`ment is broken up into the following 12 sections:
`
`1. ARC]-[l'I'ECI‘URAL OVERVIEW (FIG. 1):
`2. OVERVIEW OF CHAT AND BBS SERVICES:
`3. OVERVIEW OF DIRECTORY SERVICE AND SECU-
`RITY (FIG. 2'}:
`4. ACCESS RIGHTS (FIGS. 3A AND 3B}:
`5. COMPRESSION BY GROUPING OF OBJECFS (FIGS.
`4A AND 4B}:
`6. COMPRESSION BY GROUPING OF USERS
`(FIGURES SA AND SB):
`‘
`7. ACCESS RIGHTS DATABASE (FIG. 6):
`8. QUERIES OF ACCESS RIGHTS DATABASE (FIGS. '7
`AND 8):
`9. ACCESS RIG]-ITS CACHE (FIG. 9):
`10. GetAccountRights MEI‘!-[OD (FIG. 10}:
`ll. ASSIGNMENT OF TOKENS AND FORMATION OF
`USER GROUPS: and
`12. OTI-tE'.R EMBODIMENTS
`
`The first of these sections provides an overview of the
`on—line services network in which the present invention is
`employed. The architecture of this network is further
`described in the above-referenced. commonly assigned
`application having the title “ARCHITECT URE FOR
`SCALABLE ON—LlNE SERVICES NETWORK" ('U.S. Ser.
`No. 08M-72.307). which is incorporated herein in by refer-
`CIICC.
`
`1. Architectural Overview (FIG. 1,:
`FIG.
`1 is a high level diagram illustrating the general
`architecture of an on-line services network 100 which pro-
`vides access control in accordance with the present inven-
`tion. Multiple client microcomputers l02 are connected to a
`host data center 104 by a wide area network (WAN) 106.
`The wide area network 106 includes WAN lines 108 which
`
`Facebook's Exhibit No. 1012
`Page 15
`
`

`
`5.94! .94?
`
`15
`
`7
`are provided by one or more telecommunications providers.
`and which allow end users (i.e.. users of the microcomputers
`102) over a wide geographic area to access the host data
`center 104. The WAN lines 108 may include. for example.
`X25 lines. TCPIIP lines. and ISDN (Integrated Service
`Digital Network] lines. The host data center 104 provides a
`variety of inforrnation—related and comrnunicationwelated
`on-line services to end users.
`The host data center 104 comprises a plurality of appli-
`cation servers 120 connected to one ormore high speed local
`area networks (LAN) 122. The application servers 120 are
`preferably Pentium-class (or better} microcomputers which
`are scalable to at least four central processing units ICPUS).
`and which run the Microsoft Windows NT operating system
`available from Microsoft Corporation. Each application
`server 120 typically has at least 123 MB of random—access
`memory [RAM] and at least 4 GB of disk space.
`The application servers 120 are arranged into service
`groups (alsoreferrod to as “AppGroups“} that correspond to
`specific on-line services. Each service group runs a particu-
`lar service and provides access to a corresponding data set.
`Three example service groups are shown in FIG. I: a CHAT
`service group 130. a bulletin board system (BBS) service
`group I32. and a Di.rSrv service group 134. Additional
`service groups (not shown) are provided to implement other
`on-line services.
`including Mediaview (a suvice which
`provides multimedia titles to end users]. Mail {an email
`service). [TM ta service for uploading and downloading
`files)and Component Managerta service which allows users
`to update client software when new releases become
`available]. Other on—line services may include. for example.
`an interactive games service. a
`tile transfer service. a
`weather service. and a